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

There are N people numbered 1 through N. Each person has a integer score called programming ability; person i's programming ability is P_i points. How many more points does person 1 need, so that person 1 becomes the strongest? In other words, what is the minimum non-negative integer x such that P_1 + x > P_i for all i \neq 1?

Constraints

• 1\leq N \leq 100
• 1\leq P_i \leq 100
• All input values are integers.

Sample Input 1

4
5 15 2 10

Sample Output 1

11

Person 1 becomes the strongest when their programming skill is 16 points or more, so the answer is 16-5=11.

Sample Input 2

4
15 5 2 10

Sample Output 2

0

Person 1 is already the strongest, so no more programming skill is needed.

Sample Input 3

3
100 100 100

Sample Output 3

1

Problem Statement

At the annual Setsubun festival, one eats the same number of beans as their age. Takahashi-kun does not eat beans at any other time.
He is N years old at this year's Setsubun (0 years later).

At the earliest, how many years later will he have eaten a total of K or more beans from this year onward (including this year)?
He is immortal, so he will eventually have eaten a total of K or more beans from this year onward.

Constraints

• All input values are integers.
• 1 \le N,K \le 10^8

Sample Input 1

4 43

Sample Output 1

6

• At Setsubun 0 years later, Takahashi-kun eats 4 beans, totaling 4 beans from this year onward.
• At Setsubun 1 year later, he eats 5 beans, totaling 9 beans from this year onward.
• At Setsubun 2 years later, he eats 6 beans, totaling 15 beans from this year onward.
• At Setsubun 3 years later, he eats 7 beans, totaling 22 beans from this year onward.
• At Setsubun 4 years later, he eats 8 beans, totaling 30 beans from this year onward.
• At Setsubun 5 years later, he eats 9 beans, totaling 39 beans from this year onward.
• At Setsubun 6 years later, he eats 10 beans, totaling 49 beans from this year onward.

At Setsubun 6 years later, he will have eaten a total of 43 or more beans, so output 6.

Sample Input 2

100000000 100000000

Sample Output 2

0

The number of beans eaten this year alone may reach K or more.

Sample Input 3

1234 12345678

Sample Output 3

3886

Problem Statement

There are N + 1 rooms arranged in a line, numbered 0, 1, \ldots, N in order.

Between the rooms, there are N doors numbered 1, 2, \ldots, N. Door i is between rooms i - 1 and i.

For each door, a value L_i representing the lock state is given. When L_i = 0, door i is unlocked, and when L_i = 1, door i is locked.

There are two people, one in room 0 and the other in room N. Each person can move between rooms i - 1 and i only when door i is unlocked.

Find the number of rooms that neither of the two people can reach.

Constraints

• 2 \leq N \leq 100
• L_i \in \lbrace 0, 1 \rbrace
• All input values are integers.

Sample Input 1

5
0 1 0 0 1

Sample Output 1

3

The rooms that neither of the two people can reach are rooms 2, 3, 4, which is 3 rooms.

Sample Input 2

3
1 0 1

Sample Output 2

2

Sample Input 3

8
0 0 1 1 0 1 0 0

Sample Output 3

3

Problem Statement

We define sequences S_n as follows.

• S_1 is a sequence of length 1 containing a single 1.
• S_n (n is an integer greater than or equal to 2) is a sequence obtained by concatenating S_{n-1}, n, S_{n-1} in this order.

For example, S_2 and S_3 is defined as follows.

• S_2 is a concatenation of S_1, 2, and S_1, in this order, so it is 1,2,1.
• S_3 is a concatenation of S_2, 3, and S_2, in this order, so it is 1,2,1,3,1,2,1.

Given N, print the entire sequence S_N.

Constraints

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

Sample Input 1

2

Sample Output 1

1 2 1

As described in the Problem Statement, S_2 is 1,2,1.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

4

Sample Output 3

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

• S_4 is a concatenation of S_3, 4, and S_3, in this order.

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S equal T by performing the following operation some number of times (possibly zero).

Between two consecutive equal characters in S, insert a character equal to these characters. That is, take the following three steps.

1. Let N be the current length of S, and S = S_1S_2\ldots S_N.
2. Choose an integer i between 1 and N-1 (inclusive) such that S_i = S_{i+1}. (If there is no such i, do nothing and terminate the operation now, skipping step 3.)
3. Insert a single copy of the character S_i(= S_{i+1}) between the i-th and (i+1)-th characters of S. Now, S is a string of length N+1: S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N.

Constraints

• Each of S and T is a string of length between 2 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

abbaac
abbbbaaac

Sample Output 1

Yes

You can make S = abbaac equal T = abbbbaaac by the following three operations.

• First, insert b between the 2-nd and 3-rd characters of S. Now, S = abbbaac.
• Next, insert b again between the 2-nd and 3-rd characters of S. Now, S = abbbbaac.
• Lastly, insert a between the 6-th and 7-th characters of S. Now, S = abbbbaaac.

Thus, Yes should be printed.

Sample Input 2

xyzz
xyyzz

Sample Output 2

No

No sequence of operations makes S = xyzz equal T = xyyzz. Thus, No should be printed.

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_N) of length N.

Process Q queries in order. Each query is in one of the following formats:

• 1 x : Swap the values of A_x and A_{x+1}.
• 2 l r : Find the value of \displaystyle \sum_{l\leq i\leq r} A_i.

Constraints

• 2\leq N \leq 2\times 10^5
• 1\leq Q \leq 5\times 10^5
• 1\leq A_i \leq 10^4
• For queries of the first type, 1\leq x \leq N-1.
• For queries of the second type, 1\leq l\leq r \leq N.
• All input values are integers.

Sample Input 1

4 4
2 7 1 8
1 2
2 1 2
1 1
2 2 4

Sample Output 1

3
17

• In the 1-st query, swap the values of A_2 and A_3. This makes A=(2,1,7,8).
• In the 2-nd query, find the value of A_1+A_2. The answer is 2+1=3.
• In the 3-rd query, swap the values of A_1 and A_2. This makes A=(1,2,7,8).
• In the 4-th query, find the value of A_2+A_3+A_4. The answer is 2+7+8=17.

Sample Input 2

8 10
22 75 26 45 72 81 47 29
2 2 7
2 6 8
2 4 4
1 2
2 1 3
1 1
2 2 4
1 2
1 4
2 1 1

Sample Output 2

346
157
45
123
142
26

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N.

For each k=1,2,\dots,N, find the remainder when the least common multiple of the N-1 elements of A excluding A_k is divided by 998244353.

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^7
• All input values are integers.
• The sum of N over all test cases in a single input is at most 2 \times 10^5.

Sample Input 1

3
5
9 12 25 8 15
8
592 26 167 912 171 321 327 651
10
9566582 2785103 1924635 359502 6912831 4893928 2820155 5071742 1836019 9037883

Sample Output 1

600 1800 360 900 1800
447582749 506009091 523568328 588652065 196217355 471970745 921220985 738745385
747032704 756838459 344127037 146466685 159487731 555429485 826726159 884617928 322846201 298477407

For the first test case, the following holds.

• The N-1 elements of A excluding A_1 are 12,25,8,15, and their least common multiple is 600.
• The N-1 elements of A excluding A_2 are 9,25,8,15, and their least common multiple is 1800.
• The N-1 elements of A excluding A_3 are 9,12,8,15, and their least common multiple is 360.
• The N-1 elements of A excluding A_4 are 9,12,25,15, and their least common multiple is 900.
• The N-1 elements of A excluding A_5 are 9,12,25,8, and their least common multiple is 1800.

Problem Statement

There is a tree with N vertices. The vertices are numbered 1, 2, \ldots, N, and the i-th edge connects vertices U_i and V_i.

Initially, all vertices are painted black.

Process Q queries of the following form in order and find the answer for each query.

• An integer x (1 \leq x \leq N) is given. If vertex x is white, repaint it black; if vertex x is black, repaint it white. Then, find the maximum distance between two black vertices. Here, the distance between two vertices on a tree is the number of edges in the simple path between them.

In the given inputs, there are always at least two black vertices when processing the queries in order.

Constraints

• 3 \leq N \leq 10^5
• 1 \leq U_i, V_i \leq N
• The given graph is a tree.
• 1 \leq Q \leq 10^5
• For each query, 1 \leq x \leq N.
• There are always at least two black vertices.
• All input values are integers.

Sample Input 1

7
1 2
2 3
2 4
6 7
3 5
7 3
9
1
4
2
6
3
1
1
4
6

Sample Output 1

4
3
3
2
2
3
2
3
4

• After the repainting in the 1st query, the black vertices are 2, 3, 4, 5, 6, 7. The distance between vertices 4 and 6 is 4, and the answer is 4.
• After the repainting in the 2nd query, the black vertices are 2, 3, 5, 6, 7. The distance between vertices 2 and 6 is 3, and the answer is 3.
• After the repainting in the 3rd query, the black vertices are 3, 5, 6, 7. The distance between vertices 5 and 6 is 3, and the answer is 3.
• After the repainting in the 4th query, the black vertices are 3, 5, 7. The distance between vertices 5 and 7 is 2, and the answer is 2.
• After the repainting in the 5th query, the black vertices are 5, 7. The distance between vertices 5 and 7 is 2, and the answer is 2.
• After the repainting in the 6th query, the black vertices are 1, 5, 7. The distance between vertices 1 and 5 is 3, and the answer is 3.
• After the repainting in the 7th query, the black vertices are 5, 7. The distance between vertices 5 and 7 is 2, and the answer is 2.
• After the repainting in the 8th query, the black vertices are 4, 5, 7. The distance between vertices 4 and 5 is 3, and the answer is 3.
• After the repainting in the 9th query, the black vertices are 4, 5, 6, 7. The distance between vertices 4 and 6 is 4, and the answer is 4.

Note that the examples given above are just one instance achieving the maximum value.