Problem Statement

You are given positive integers N, L, and R.
For a sequence A = (1, 2, \dots, N) of length N, an operation of reversing the L-th through R-th elements was performed once.
Print the sequence after this operation.

Constraints

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

Sample Input 1

5 2 3

Sample Output 1

1 3 2 4 5

Initially, A = (1, 2, 3, 4, 5).
After reversing the second through third elements, the sequence becomes (1, 3, 2, 4, 5), which should be printed.

Sample Input 2

7 1 1

Sample Output 2

1 2 3 4 5 6 7

It is possible that L = R.

Sample Input 3

10 1 10

Sample Output 3

10 9 8 7 6 5 4 3 2 1

It is possible that L = 1 or R = N.

Problem Statement

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

Extract all elements of A that are multiples of K, divide them by K, and print the quotients.

Constraints

• 1\leq N,K\leq 100
• 1\leq A_1 < A_2 < \ldots < A_N \leq 100
• A has at least one multiple of K.
• All given numbers are integers.

Sample Input 1

5 2
2 5 6 7 10

Sample Output 1

1 3 5

The multiples of 2 among the elements in A are 2, 6, and 10. Divide them by 2 to get 1, 3, and 5, and print them in ascending order with spaces in between.

Sample Input 2

3 1
3 4 7

Sample Output 2

3 4 7

Sample Input 3

5 10
50 51 54 60 65

Sample Output 3

5 6

Problem Statement

Two dice, each with six faces 1,2,3,4,5,6, are rolled. Find the probability that at least one of the following two conditions holds:

• The sum of the two outcomes is at least X.
• The absolute difference of the two outcomes is at least Y.

Each face of each die is equally likely, and the two dice are independent.

Constraints

• 2 \le X \le 13
• 0 \le Y \le 6
• All input values are integers.

Sample Input 1

9 3

Sample Output 1

0.555555555555555555555555555555

Let (x,y) denote the event that the dice show x and y.

• The sum is at least 9 for (3,6),(4,5),(4,6),(5,4),(5,5),(5,6),(6,3),(6,4),(6,5),(6,6).
• The difference is at least 3 for (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(5,1),(5,2),(6,1),(6,2),(6,3).

At least one of these conditions holds for the following 20 pairs: (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(4,5),(4,6),(5,1),(5,2),(5,4),(5,5),(5,6),(6,1),(6,2),(6,3),(6,4),(6,5),(6,6).

Thus, the answer is \dfrac{20}{36}=\dfrac59=0.5555555555\ldots.

Because an absolute error of at most 10^{-9} is allowed, outputs such as 0.5555555565 or 0.55555555456789 are accepted.

Sample Input 2

13 6

Sample Output 2

0

Neither the sum of two dice can be 13 or greater, nor can their difference be 6 or greater.

Thus, the answer is 0.

Sample Input 3

10 3

Sample Output 3

0.5

Problem Statement

There are N people whose IDs are 1, 2, \ldots, and N.

Each of person 1, person 2, \ldots, and person N performs the following action once in this order:

• If person i's ID has not been called out yet, call out person A_i's ID.

Enumerate the IDs of all the people whose IDs are never called out until the end in ascending order.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq N
• A_i \neq i
• All values in the input are integers.

Sample Input 1

5
3 1 4 5 4

Sample Output 1

2
2 4

The five people's actions are as follows.

• Person 1's ID has not been called out yet, so person 1 calls out person 3's ID.
• Person 2's ID has not been called out yet, so person 2 calls out person 1's ID.
• Person 3's ID has already been called out by person 1, so nothing happens.
• Person 4's ID has not been called out yet, so person 4 calls out person 5's ID.
• Person 5's ID has already been called out by person 4, so nothing happens.

Therefore, person 2 and 4's IDs are not called out until the end.

Sample Input 2

20
9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12

Sample Output 2

10
1 2 5 6 8 11 14 17 18 20

Problem Statement

N students are taking a 4-day exam.

There is a 300-point test on each day, for a total of 1200 points.

The first three days of the exam are already over, and the fourth day is now about to begin. The i-th student (1 \leq i \leq N) got P_{i, j} points on the j-th day (1 \leq j \leq 3).

For each student, determine whether it is possible that he/she is ranked in the top K after the fourth day.
Here, the rank of a student after the fourth day is defined as the number of students whose total scores over the four days are higher than that of the student, plus 1.

Constraints

• 1 \leq K \leq N \leq 10^5
• 0 \leq P_{i, j} \leq 300 \, (1 \leq i \leq N, 1 \leq j \leq 3)
• All values in input are integers.

Sample Input 1

3 1
178 205 132
112 220 96
36 64 20

Sample Output 1

Yes
Yes
No

If every student scores 100 on the fourth day, the 1-st student will rank 1-st.
If the 2-nd student scores 100 and the other students score 0 on the fourth day, the 2-nd student will rank 1-st.
The 3-rd student will never rank 1-st.

Sample Input 2

2 1
300 300 300
200 200 200

Sample Output 2

Yes
Yes

Sample Input 3

4 2
127 235 78
192 134 298
28 56 42
96 120 250

Sample Output 3

Yes
Yes
No
Yes

Problem Statement

There is an N \times N grid, where the cell at the i-th row from the top and the j-th column from the left contains the integer N \times (i-1) + j.

Over T turns, integers will be announced. On Turn i, the integer A_i is announced, and the cell containing A_i is marked. Determine the turn on which Bingo is achieved for the first time. If Bingo is not achieved within T turns, print -1.

Here, achieving Bingo means satisfying at least one of the following conditions:

• There exists a row in which all N cells are marked.
• There exists a column in which all N cells are marked.
• There exists a diagonal line (from top-left to bottom-right or from top-right to bottom-left) in which all N cells are marked.

Constraints

• 2 \leq N \leq 2 \times 10^3
• 1 \leq T \leq \min(N^2, 2 \times 10^5)
• 1 \leq A_i \leq N^2
• A_i \neq A_j if i \neq j.
• All input values are integers.

Sample Input 1

3 5
5 1 8 9 7

Sample Output 1

4

The state of the grid changes as follows. Bingo is achieved for the first time on Turn 4.

Sample Input 2

3 5
4 2 9 7 5

Sample Output 2

-1

Bingo is not achieved within five turns, so print -1.

Sample Input 3

4 12
13 9 6 5 2 7 16 14 8 3 10 11

Sample Output 3

9

Problem Statement

You are given length-N lowercase English strings S and T, and M pairs of integers (L_1,R_1),(L_2,R_2),\ldots,(L_M,R_M).

Perform the following operation for i=1,2,\ldots,M in order:

• Swap the L_i-th through R_i-th characters of S and the L_i-th through R_i-th characters of T.
  • For example, if S is abcdef, T is ghijkl, and (L_i,R_i)=(3,5), then S and T become abijkf and ghcdel, respectively.

Find the string S after performing the M operations.

Constraints

• 1\leq N\leq 5\times 10^5
• 1\leq M\leq 2\times 10^5
• Each of S and T is a length-N lowercase English strings.
• 1\leq L_i\leq R_i\leq N
• N, M, L_i, and R_i are integers.

Sample Input 1

5 3
apple
lemon
2 4
1 5
5 5

Sample Output 1

lpple

Initially, S and T are apple and lemon, respectively.

• After the operation for i=1, S and T are aemoe and lppln, respectively.
• After the operation for i=2, S and T are lppln and aemoe, respectively.
• After the operation for i=3, S and T are lpple and aemon, respectively.

Thus, the string S after the three operations is lpple.

Sample Input 2

10 5
lemwrbogje
omsjbfggme
5 8
4 8
1 3
6 6
1 4

Sample Output 2

lemwrfogje

Problem Statement

For strings x and y, define f(x, y) as follows:

• f(x, y) is the length of the longest common prefix of x and y.

You are given N strings (S_1, \ldots, S_N) consisting of lowercase English letters. Find the value of the following expression:

Constraints

• 2 \leq N \leq 3\times 10^5
• S_i is a string consisting of lowercase English letters.
• 1 \leq |S_i|
• |S_1|+|S_2|+\ldots+|S_N|\leq 3\times 10^5
• All input numbers are integers.

Sample Input 1

3
ab abc arc

Sample Output 1

4

• f(S_1,S_2)=2
• f(S_1,S_3)=1
• f(S_2,S_3)=1

Thus, the answer is f(S_1,S_2) + f(S_1,S_3) + f(S_2,S_3) = 4.

Sample Input 2

11
ab bb aaa bba baba babb aaaba aabbb a a b

Sample Output 2

32

Problem Statement

Given are sequences of N integers each: A = (A_1, \dots, A_N) and B = (B_1, \dots, B_N). Find the number of non-empty subsets S of \{1,2,\ldots,N\} that satisfy the following condition:

• \max_{i \in S} A_i \geq \sum_{i \in S} B_i.

Since the count can be enormous, print it modulo 998244353.

Constraints

• 1 \leq N \leq 5000
• 1 \leq A_i,B_i \leq 5000
• All values in input are integers.

Sample Input 1

2
3 1
1 2

Sample Output 1

2

\{1,2,\ldots,N\} has three subsets: \{1\}, \{2\}, and \{1,2\}.

• For S=\{1\}, we have \max_{i \in S} A_i=3 and \sum_{i \in S} B_i=1.
• For S=\{2\}, we have \max_{i \in S} A_i=1 and \sum_{i \in S} B_i=2.
• For S=\{1,2\}, we have \max_{i \in S} A_i=3 and \sum_{i \in S} B_i=3.

Thus, the condition \max_{i \in S} A_i \geq \sum_{i \in S} B_i is satisfied by two subsets: \{1\} and \{1,2\}.

Sample Input 2

2
1 1
2 2

Sample Output 2

0

There may be no subsets that satisfy the condition.

Sample Input 3

20
1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247
4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017

Sample Output 3

476