Problem Statement

This is the 214-th AtCoder Beginner Contest (ABC).

The ABCs so far have had the following number of problems.

• The 1-st through 125-th ABCs had 4 problems each.
• The 126-th through 211-th ABCs had 6 problems each.
• The 212-th through 214-th ABCs have 8 problems each.

Find the number of problems in the N-th ABC.

Constraints

• 1 \leq N \leq 214
• All values in input are integers.

Sample Input 1

214

Sample Output 1

8

Sample Input 2

1

Sample Output 2

4

Sample Input 3

126

Sample Output 3

6

Problem Statement

You are given a string S of length N consisting of three kinds of characters: ., |, and *. S contains exactly two | and exactly one *.

Determine whether the * is between the two |, and if so, print in; otherwise, print out.

More formally, determine whether one of the characters before the * is | and one of the characters after the * is |.

Constraints

• 3\leq N\leq 100
• N is an integer.
• S is a string of length N consisting of ., |, and *.
• S contains exactly two |.
• S contains exactly one *.

Sample Input 1

10
.|..*...|.

Sample Output 1

in

Between the two |, we have |..*...|, which contains *, so you should print in.

Sample Input 2

10
.|..|.*...

Sample Output 2

out

Between the two |, we have |..|, which does not contain *, so you should print out.

Sample Input 3

3
|*|

Sample Output 3

in

Problem Statement

Keyence has N bases worldwide, numbered 1 to N. Base i has W_i employees, and at 0 o'clock in Coordinated Universal Time (UTC), it is X_i o'clock at base i.

You want to hold a one-hour meeting across the entire company. Each employee can only participate in the meeting if the meeting time is completely within the 9:00-18:00 time slot at their base. Find the maximum number of employees who can participate when deciding the meeting time to allow as many employees as possible to participate.

Constraints

• 1\leq N \leq 1000
• 1\leq W_i \leq 10^6
• 0\leq X_i < 24
• All input values are integers.

Sample Input 1

3
5 0
3 3
2 18

Sample Output 1

8

Consider holding the meeting from 14:00 to 15:00 in UTC.

• The meeting is held from 14:00 to 15:00 at base 1, so the 5 employees at base 1 can participate in the meeting.
• The meeting is held from 17:00 to 18:00 at base 2, so the 3 employees at base 2 can participate in the meeting.
• The meeting is held from 8:00 to 9:00 at base 3, so the 2 employees at base 3 cannot participate in the meeting.

Thus, a total of 5+3=8 employees can participate in the meeting. No meeting time allows more employees to participate.

Sample Input 2

2
1 10
1000000 20

Sample Output 2

1000000

Sample Input 3

6
31 3
20 8
11 5
4 3
47 14
1 18

Sample Output 3

67

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_N) of length N and a sequence B=(B_1,B_2,\dots,B_M) of length M. Here, all elements of A and B are pairwise distinct. Determine whether the sequence C=(C_1,C_2,\dots,C_{N+M}) formed by sorting all elements of A and B in ascending order contains two consecutive elements appearing in A.

Constraints

• 1 \leq N, M \leq 100
• 1 \leq A_i, B_j \leq 200
• A_1, A_2, \dots, A_N, B_1, B_2, \dots, B_M are distinct.
• All input values are integers.

Sample Input 1

3 2
3 2 5
4 1

Sample Output 1

Yes

C=(1,2,3,4,5). Since 2 and 3 from A occur consecutively in C, print Yes.

Sample Input 2

3 2
3 1 5
4 2

Sample Output 2

No

C=(1,2,3,4,5). Since no two elements from A occur consecutively in C, print No.

Sample Input 3

1 1
1
2

Sample Output 3

No

Problem Statement

Takahashi runs an SNS "Twidai," which has N users from user 1 through user N. In Twidai, users can follow or unfollow other users.

Q operations have been performed since Twidai was launched. The i-th (1\leq i\leq Q) operation is represented by three integers T_i, A_i, and B_i, whose meanings are as follows:

• If T_i = 1: it means that user A_i follows user B_i. If user A_i is already following user B_i at the time of this operation, it does not make any change.
• If T_i = 2: it means that user A_i unfollows user B_i. If user A_i is not following user B_i at the time of this operation, it does not make any change.
• If T_i = 3: it means that you are asked to determine if users A_i and B_i are following each other. You need to print Yes if user A_i is following user B_i and user B_i is following user A_i, and No otherwise.

When the service was launched, no users were following any users.

Print the correct answers for all operations such that T_i = 3 in ascending order of i.

Constraints

• 2 \leq N \leq 10 ^ 9
• 1 \leq Q \leq 2\times10 ^ 5
• T _ i=1,2,3\ (1\leq i\leq Q)
• 1 \leq A _ i \leq N\ (1\leq i\leq Q)
• 1 \leq B _ i \leq N\ (1\leq i\leq Q)
• A _ i\neq B _ i\ (1\leq i\leq Q)
• There exists i\ (1\leq i\leq Q) such that T _ i=3.
• All values in the input are integers.

Sample Input 1

3 9
1 1 2
3 1 2
1 2 1
3 1 2
1 2 3
1 3 2
3 1 3
2 1 2
3 1 2

Sample Output 1

No
Yes
No
No

Twidai has three users. The nine operations are as follows.

• User 1 follows user 2. No other users are following or followed by any users.
• Determine if users 1 and 2 are following each other. User 1 is following user 2, but user 2 is not following user 1, so No is the correct answer to this operation.
• User 2 follows user 1.
• Determine if users 1 and 2 are following each other. User 1 is following user 2, and user 2 is following user 1, so Yes is the correct answer to this operation.
• User 2 follows user 3.
• User 3 follows user 2.
• Determine if users 1 and 3 are following each other. User 1 is not following user 3, and user 3 is not following user 1, so No is the correct answer to this operation.
• User 1 unfollows user 2.
• Determine if users 1 and 2 are following each other. User 2 is following user 1, but user 1 is not following user 2, so No is the correct answer to this operation.

Sample Input 2

2 8
1 1 2
1 2 1
3 1 2
1 1 2
1 1 2
1 1 2
2 1 2
3 1 2

Sample Output 2

Yes
No

A user may follow the same user multiple times.

Sample Input 3

10 30
3 1 6
3 5 4
1 6 1
3 1 7
3 8 4
1 1 6
2 4 3
1 6 5
1 5 6
1 1 8
1 8 1
2 3 10
1 7 6
3 5 6
1 6 7
3 6 7
1 9 5
3 8 6
3 3 8
2 6 9
1 7 1
3 10 8
2 9 2
1 10 9
2 6 10
2 6 8
3 1 6
3 1 8
2 8 5
1 9 10

Sample Output 3

No
No
No
No
Yes
Yes
No
No
No
Yes
Yes

Problem Statement

Your refrigerator has N kinds of ingredients. Let us call them ingredient 1, \dots, ingredient N. You have Q_i grams of ingredient i.

You can make two types of dishes. To make one serving of dish A, you need A_i grams of each ingredient i (1 \leq i \leq N). To make one serving of dish B, you need B_i grams of each ingredient i. You can only make an integer number of servings of each type of dish.

Using only the ingredients in the refrigerator, what is the maximum total number of servings of dishes you can make?

Constraints

• 1 \leq N \leq 10
• 1 \leq Q_i \leq 10^6
• 0 \leq A_i \leq 10^6
• There is an i such that A_i \geq 1.
• 0 \leq B_i \leq 10^6
• There is an i such that B_i \geq 1.
• All input values are integers.

Sample Input 1

2
800 300
100 100
200 10

Sample Output 1

5

This refrigerator has 800 grams of ingredient 1 and 300 grams of ingredient 2.

You can make one serving of dish A with 100 grams of ingredient 1 and 100 grams of ingredient 2, and one serving of dish B with 200 grams of ingredient 1 and 10 grams of ingredient 2.

To make two servings of dish A and three servings of dish B, you need 100 \times 2 + 200 \times 3 = 800 grams of ingredient 1, and 100 \times 2 + 10 \times 3 = 230 grams of ingredient 2, neither of which exceeds the amount available in the refrigerator. In this way, you can make a total of five servings of dishes, but there is no way to make six, so the answer is 5.

Sample Input 2

2
800 300
100 0
0 10

Sample Output 2

38

You can make 8 servings of dish A with 800 grams of ingredient 1, and 30 servings of dish B with 300 grams of ingredient 2, for a total of 38 servings.

Sample Input 3

2
800 300
801 300
800 301

Sample Output 3

0

You cannot make any dishes.

Sample Input 4

10
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

Sample Output 4

222222

Problem Statement

We have an infinite hexagonal grid shown below. Initially, all squares are white.

A hexagonal cell is represented as (i,j) with two integers i and j.
Cell (i,j) is adjacent to the following six cells:

• (i-1,j-1)
• (i-1,j)
• (i,j-1)
• (i,j+1)
• (i+1,j)
• (i+1,j+1)

Takahashi has painted N cells (X_1,Y_1),(X_2,Y_2),\dots,(X_N,Y_N) black.
Find the number of connected components formed by the black cells.
Two black cells belong to the same connected component when one can travel between those two black cells by repeatedly moving to an adjacent black cell.

Constraints

• All values in the input are integers.
• 1 \le N \le 1000
• |X_i|,|Y_i| \le 1000
• The pairs (X_i,Y_i) are distinct.

Sample Input 1

6
-1 -1
0 1
0 2
1 0
1 2
2 0

Sample Output 1

3

After Takahashi paints cells black, the grid looks as shown below.

The black squares form the following three connected components:

• (-1,-1)
• (1,0),(2,0)
• (0,1),(0,2),(1,2)

Sample Input 2

4
5 0
4 1
-3 -4
-2 -5

Sample Output 2

4

Sample Input 3

5
2 1
2 -1
1 0
3 1
1 -1

Sample Output 3

1

Problem Statement

In the country of AtCoder, there are N stations: station 1, station 2, \ldots, station N.

You are given M pieces of information about trains in the country. The i-th piece of information (1\leq i\leq M) is represented by a tuple of six positive integers (l _ i,d _ i,k _ i,c _ i,A _ i,B _ i), which corresponds to the following information:

• For each t=l _ i,l _ i+d _ i,l _ i+2d _ i,\ldots,l _ i+(k _ i-1)d _ i, there is a train as follows:
  • The train departs from station A _ i at time t and arrives at station B _ i at time t+c _ i.

No trains exist other than those described by this information, and it is impossible to move from one station to another by any means other than by train.
Also, assume that the time required for transfers is negligible.

Let f(S) be the latest time at which one can arrive at station N from station S.
More precisely, f(S) is defined as the maximum value of t for which there is a sequence of tuples of four integers \big((t _ i,c _ i,A _ i,B _ i)\big) _ {i=1,2,\ldots,k} that satisfies all of the following conditions:

• t\leq t _ 1
• A _ 1=S,B _ k=N
• B _ i=A _ {i+1} for all 1\leq i\lt k,
• For all 1\leq i\leq k, there is a train that departs from station A _ i at time t _ i and arrives at station B _ i at time t _ i+c _ i.
• t _ i+c _ i\leq t _ {i+1} for all 1\leq i\lt k.

If no such t exists, set f(S)=-\infty.

Find f(1),f(2),\ldots,f(N-1).

Constraints

• 2\leq N\leq2\times10 ^ 5
• 1\leq M\leq2\times10 ^ 5
• 1\leq l _ i,d _ i,k _ i,c _ i\leq10 ^ 9\ (1\leq i\leq M)
• 1\leq A _ i,B _ i\leq N\ (1\leq i\leq M)
• A _ i\neq B _ i\ (1\leq i\leq M)
• All input values are integers.

Sample Input 1

6 7
10 5 10 3 1 3
13 5 10 2 3 4
15 5 10 7 4 6
3 10 2 4 2 5
7 10 2 3 5 6
5 3 18 2 2 3
6 3 20 4 2 1

Sample Output 1

55
56
58
60
17

The following diagram shows the trains running in the country (information about arrival and departure times is omitted).

Consider the latest time at which one can arrive at station 6 from station 2. As shown in the following diagram, one can arrive at station 6 by departing from station 2 at time 56 and moving as station 2\rightarrow station 3\rightarrow station 4\rightarrow station 6.

It is impossible to depart from station 2 after time 56 and arrive at station 6, so f(2)=56.

Sample Input 2

5 5
1000000000 1000000000 1000000000 1000000000 1 5
5 9 2 6 2 3
10 4 1 6 2 3
1 1 1 1 3 5
3 1 4 1 5 1

Sample Output 2

1000000000000000000
Unreachable
1
Unreachable

There is a train that departs from station 1 at time 10 ^ {18} and arrives at station 5 at time 10 ^ {18}+10 ^ 9. There are no trains departing from station 1 after that time, so f(1)=10 ^ {18}. As seen here, the answer may not fit within a 32\operatorname{bit} integer.

Also, both the second and third pieces of information guarantee that there is a train that departs from station 2 at time 14 and arrives at station 3 at time 20. As seen here, some trains may appear in multiple pieces of information.

Sample Input 3

16 20
4018 9698 2850 3026 8 11
2310 7571 7732 1862 13 14
2440 2121 20 1849 11 16
2560 5115 190 3655 5 16
1936 6664 39 8822 4 16
7597 8325 20 7576 12 5
5396 1088 540 7765 15 1
3226 88 6988 2504 13 5
1838 7490 63 4098 8 3
1456 5042 4 2815 14 7
3762 6803 5054 6994 10 9
9526 6001 61 8025 7 8
5176 6747 107 3403 1 5
2014 5533 2031 8127 8 11
8102 5878 58 9548 9 10
3788 174 3088 5950 3 13
7778 5389 100 9003 10 15
556 9425 9458 109 3 11
5725 7937 10 3282 2 9
6951 7211 8590 1994 15 12

Sample Output 3

720358
77158
540926
255168
969295
Unreachable
369586
466218
343148
541289
42739
165772
618082
16582
591828

Problem Statement

There is a graph with N + Q vertices, numbered 1, 2, \ldots, N + Q. Initially, the graph has no edges.

For this graph, perform the following operation for i = 1, 2, \ldots, Q in order:

• For each integer j satisfying L_i \leq j \leq R_i, add an undirected edge with cost C_i between vertices N + i and j.

Determine if the graph is connected after all operations are completed. If it is connected, find the cost of a minimum spanning tree of the graph.

A minimum spanning tree is a spanning tree with the smallest possible cost, and the cost of a spanning tree is the sum of the costs of the edges used in the spanning tree.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq N
• 1 \leq C_i \leq 10^9
• All input values are integers.

Sample Input 1

4 3
1 2 2
1 3 4
2 4 5

Sample Output 1

22

The following edges form a minimum spanning tree:

• An edge with cost 2 connecting vertices 1 and 5
• An edge with cost 2 connecting vertices 2 and 5
• An edge with cost 4 connecting vertices 1 and 6
• An edge with cost 4 connecting vertices 3 and 6
• An edge with cost 5 connecting vertices 3 and 7
• An edge with cost 5 connecting vertices 4 and 7

Since 2 + 2 + 4 + 4 + 5 + 5 = 22, print 22.

Sample Input 2

6 2
1 2 10
4 6 10

Sample Output 2

-1

The graph is disconnected.

Sample Input 3

200000 4
1 200000 1000000000
1 200000 998244353
1 200000 999999999
1 200000 999999999

Sample Output 3

199651870599998