Problem Statement

You are given N integers A_1,A_2,\dots, and A_N.

Find the sum of the N integers.

Constraints

• 1 \le N \le 100
• 1 \le A_i \le 100
• All values in the input are integers.

Sample Input 1

3
2 7 2

Sample Output 1

11

You are given three integers: 2, 7, and 2.

The answer is 2 + 7 + 2 = 11.

Sample Input 2

1
3

Sample Output 2

3

Problem Statement

Print all non-negative integers less than or equal to N in descending order.

Constraints

• 1 \leq N \leq 100
• N is an integer.

Sample Input 1

3

Sample Output 1

3
2
1
0

We have four non-negative integers less than or equal to 3, which are 0, 1, 2, and 3.
To print them in descending order, print 3 in the first line, 2 in the second, 1 in the third, and 0 in the fourth.

Sample Input 2

22

Sample Output 2

22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

Problem Statement

You are given a string S consisting of . and #.

Among all strings T that satisfy all of the following conditions, find one with the maximum number of os.

• The length of T is equal to the length of S.
• T consists of ., #, or o.
• T_i= # if and only if S_i= #.
• If T_i=T_j= o (i < j), then there exists at least one # among T_{i+1},\ldots,T_{j-1}.

Constraints

• S is a string consisting of . and # with length between 1 and 100, inclusive.

Sample Input 1

#..#.

Sample Output 1

#o.#o

Setting T= #o.#o satisfies all conditions.

There is no string T that satisfies all conditions and has more than two os, so outputting #o.#o is correct.

Outputting #.o#o is also correct.

Sample Input 2

#

Sample Output 2

#

Sample Input 3

.....

Sample Output 3

..o..

Outputting o...., .o..., ...o., or ....o is also correct.

Sample Input 4

...#..#.##.#.

Sample Output 4

o..#.o#o##o#o

Problem Statement

The AtCoder amusement park has an attraction that can accommodate K people. Now, there are N groups lined up in the queue for this attraction.

The i-th group from the front (1\leq i\leq N) consists of A_i people. For all i (1\leq i\leq N), it holds that A_i \leq K.

Takahashi, as a staff member of this attraction, will guide the groups in the queue according to the following procedure.

Initially, no one has been guided to the attraction, and there are K empty seats.

1. If there are no groups in the queue, start the attraction and end the guidance.
2. Compare the number of empty seats in the attraction with the number of people in the group at the front of the queue, and do one of the following:
   • If the number of empty seats is less than the number of people in the group at the front, start the attraction. Then, the number of empty seats becomes K again.
   • Otherwise, guide the entire group at the front of the queue to the attraction. The front group is removed from the queue, and the number of empty seats decreases by the number of people in the group.
3. Go back to step 1.

Here, no additional groups will line up after the guidance has started. Under these conditions, it can be shown that this procedure will end in a finite number of steps.

Determine how many times the attraction will be started throughout the guidance.

Constraints

• 1\leq N\leq 100
• 1\leq K\leq 100
• 1\leq A_i\leq K\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

7 6
2 5 1 4 1 2 3

Sample Output 1

4

Initially, the seven groups are lined up as follows:

Part of Takahashi's guidance is shown in the following figure:

• Initially, the group at the front has 2 people, and there are 6 empty seats. Thus, he guides the front group to the attraction, leaving 4 empty seats.
• Next, the group at the front has 5 people, which is more than the 4 empty seats, so the attraction is started.
• After the attraction is started, there are 6 empty seats again, so the front group is guided to the attraction, leaving 1 empty seat.
• Next, the group at the front has 1 person, so they are guided to the attraction, leaving 0 empty seats.

In total, he starts the attraction four times before the guidance is completed. Therefore, print 4.

Sample Input 2

7 10
1 10 1 10 1 10 1

Sample Output 2

7

Sample Input 3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

Sample Output 3

8

Problem Statement

Takahashi is playing a game. This game has N skills numbered 1 through N.

You are given N pairs of integers (A_1,B_1), \dots,(A_N,B_N).
If (A_i,B_i)=(0,0), then Takahashi has already learned skill i.
Otherwise, Takahashi can learn skill i if and only if at least one of skills A_i and B_i has already been learned.

Including the skills already learned, find the number of skills that Takahashi can ultimately learn.

Constraints

• 1\leq N \leq 2\times 10^5
• (A_i,B_i)=(0,0) or 1\leq A_i,B_i \leq N
• All input values are integers.

Sample Input 1

6
0 0
1 3
3 2
5 5
4 6
6 4

Sample Output 1

3

At first, Takahashi has already learned skill 1. Because skill 1 has been learned, skill 2 can be learned, and learning skill 2 enables learning skill 3. Since it is impossible to learn skills 4,5,6, the answer is 3.

Sample Input 2

4
0 0
0 0
0 0
0 0

Sample Output 2

4

Problem Statement

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

• X is an N-digit positive integer.
• Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
  • 1 \le X_i \le 9 for all integers 1 \le i \le N;
  • |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.

Constraints

• N is an integer.
• 2 \le N \le 10^6

Sample Input 1

4

Sample Output 1

203

Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.

Sample Input 2

2

Sample Output 2

25

Sample Input 3

1000000

Sample Output 3

248860093

Be sure to find the count modulo 998244353.

Problem Statement

You are given three positive integers N, M, and K. Here, N and M are different.
Print the K-th smallest positive integer divisible by exactly one of N and M.

Constraints

• 1 \leq N, M \leq 10^8
• 1 \leq K \leq 10^{10}
• N \neq M
• N, M, and K are integers.

Sample Input 1

2 3 5

Sample Output 1

9

The positive integers divisible by exactly one of 2 and 3 are 2, 3, 4, 8, 9, 10, \ldots in ascending order.
Note that 6 is not included because it is divisible by both 2 and 3.
The fifth smallest positive integer that satisfies the condition is 9, so we print 9.

Sample Input 2

1 2 3

Sample Output 2

5

The numbers that satisfy the condition are 1, 3, 5, 7, \ldots in ascending order.

Sample Input 3

100000000 99999999 10000000000

Sample Output 3

500000002500000000

Problem Statement

Happy New Year! When it comes to outdoor play on New Year's, it's kite flying!

N people numbered 1 to N are trying to fly kites by the riverbank.
The river facing the riverbank flows in a straight line, so from now on, we consider a two-dimensional coordinate system where the x-axis is the direction of the river and the y-axis is the height direction.
Person i is standing at point (A_i, 0) and trying to fly a kite at point (B_i, 1).
However, to avoid collisions of people and kites, and to avoid kite strings getting tangled, persons i and j (i \neq j) cannot fly kites at the same time if the following condition is satisfied:

• The "line segment connecting (A_i, 0) and (B_i, 1)" and the "line segment connecting (A_j, 0) and (B_j, 1)" have an intersection point. (This includes the case where the endpoints of the line segments touch each other.)

What is the maximum number of people who can fly kites at the same time while respecting the above constraint?

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq A_i \leq 10^9
• 0 \leq B_i \leq 10^9
• All input values are integers.

Sample Input 1

3
3 5
1 4
2 6

Sample Output 1

2

Persons 1 and 2, as well as persons 2 and 3, can fly kites at the same time, but persons 1 and 3 cannot fly kites at the same time.
Therefore, two people, if chosen appropriately, can fly kites at the same time, while it is impossible for three people to fly kites at the same time. Thus, the answer is 2.

Sample Input 2

5
1 2
1 3
1 4
1 5
1 6

Sample Output 2

1

Sample Input 3

10
440423913 766294629
725560240 59187619
965580535 585990756
550925213 623321125
549392044 122410708
21524934 690874816
529970099 244587368
757265587 736247509
576136367 993115118
219853537 21553211

Sample Output 3

4

Problem Statement

There are N boxes numbered 1,2,\ldots,N, and 10^{100} balls numbered 1,2,\dots,10^{100}. Initially, box i contains just ball i.

Process a total of Q operations that will be performed.

There are three types of operations: 1, 2, and 3.

Type 1: Put all contents of box Y into box X. It is guaranteed that X \neq Y.

1 X Y

Type 2: Put ball k+1 into box X, where k is the current total number of balls contained in the boxes.

2 X

Type 3: Report the number of the box that contains ball X.

3 X

Constraints

• All values in the input are integers.
• 2 \le N \le 3 \times 10^5
• 1 \le Q \le 3 \times 10^5
• For each type-1 operation, 1 \le X,Y \le N and X \neq Y.
• For each type-2 operation, 1 \le X \le N.
• For each type-3 operation, ball X is contained in some box at that point.
• There is at least one type-3 operation.

Sample Input 1

5 10
3 5
1 1 4
2 1
2 4
3 7
1 3 1
3 4
1 1 4
3 7
3 6

Sample Output 1

5
4
3
1
3

This input contains ten operations.

• The first operation is of type 3. Ball 5 is in box 5.
• The second operation is of type 1. Put all contents of box 4 into box 1.
  • Box 1 now contains balls 1 and 4, and box 4 is now empty.
• The third operation is of type 2. Put ball 6 into box 1.
• The fourth operation is of type 2. Put ball 7 into box 4.
• The fifth operation is of type 3. Ball 7 is in box 4.
• The sixth operation is of type 1. Put all contents of box 1 into box 3.
  • Box 3 now contains balls 1, 3, 4, and 6, and box 1 is now empty.
• The seventh operation is of type 3. Ball 4 is in box 3.
• The eighth operation is of type 1. Put all contents of box 4 into box 1.
  • Box 1 now contains ball 7, and box 4 is now empty.
• The ninth operation is of type 3. Ball 7 is in box 1.
• The tenth operation is of type 3. Ball 6 is in box 3.