Problem Statement

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

After that, an integer X between 1 and N, inclusive, is given.

Output the value of A_X.

Constraints

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

Sample Input 1

5
1 2 3 4 5
3

Sample Output 1

3

We have (A_1, A_2, A_3, A_4 , A_5) = (1, 2, 3, 4, 5). Since A_3 = 3, output 3.

Sample Input 2

10
6 6 9 6 10 5 7 2 8 2
4

Sample Output 2

6

Sample Input 3

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

Sample Output 3

1

Problem Statement

You are given N sequences A_1, A_2, \ldots, A_N.

The length of sequence A_i is L_i, and A_i = (A_{i,1}, A_{i,2}, \ldots, A_{i,L_i}).

After that, integers X and Y are given. Output the value of A_{X,Y}.

Constraints

• 1 \le N \le 2 \times 10^5
• 1 \le L_i
• The sum of L_i is at most 2 \times 10^5.
• 1 \le A_{i,j} \le 1000
• 1 \le X \le N
• 1 \le Y \le L_X
• All input values are integers.

Sample Input 1

3
3 10 20 30
1 7
4 5 6 7 8
3 4

Sample Output 1

8

We have (A_1, A_2, A_3) = ((10,20,30), (7), (5,6, 7,8)).
Since A_3 = (5, 6, 7, 8) and A_{3,4} = 8, output 8.

Sample Input 2

4
2 9 1
3 8 2 6
1 5
2 4 3
2 2

Sample Output 2

2

Since A_2 = (8, 2, 6), we have A_{2,2} = 2.

Sample Input 3

1
5 100 200 300 400 500
1 5

Sample Output 3

500

Problem Statement

You are given integers N and K, along with N integer sequences A_1, A_2, \ldots, A_N and a length-N integer sequence C = (C_1, C_2, \ldots, C_N). The length of integer sequence A_i is L_i, and A_i = (A_{i,1}, A_{i,2}, \ldots, A_{i,L_i}). It is guaranteed that \displaystyle 1 \le K \le \sum_{i=1}^N C_iL_i.

Construct an integer sequence B = (B_1, B_2, \ldots, B_{\sum_{i=1}^N C_iL_i}) from A and C using the following procedure.

• Let B be an integer sequence of length 0.
• For i = 1, 2, \ldots, N in this order, perform the following operation:
  • Do this C_i times: append A_i to the end of B.

Find the value of B_K.

Constraints

• 1 \le N
• 1 \le L_i
• \displaystyle \sum_{i=1}^N L_i \le 2 \times 10^5
• 1 \le A_{i,j} \le 10^9 (1 \le j \le L_i)
• 1 \le C_i \le 10^9
• \displaystyle 1 \le K \le \sum_{i=1}^N C_iL_i
• All input values are integers.

Sample Input 1

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

Sample Output 1

4

B is constructed as follows:

• Let B = ().
• Append A_1 to the end of B once. We get B = (1, 3, 2).
• Append A_2 to the end of B three times. We get B = (1, 3, 2, 3, 3, 3).
• Append A_3 to the end of B twice. We get B = (1, 3, 2, 3, 3, 3, 4, 3, 4, 3).

For B = (1, 3, 2, 3, 3, 3, 4, 3, 4, 3), we have B_9 = 4, so output 4.

Sample Input 2

3 1
1 7
1 111
1 5
1 100 10000

Sample Output 2

7

Sample Input 3

3 3163812
5 1 2 3 4 5
4 9 8 7 6
2 10 11
87043 908415 9814

Sample Output 3

9

Problem Statement

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

You can perform the following operation between 0 and K times, inclusive.

• Choose an integer i satisfying 1 \le i \le N, and add i to A_i.

Find the maximum possible value of \displaystyle \min_{1 \le i \le N} A_i for the sequence after the operations.

Constraints

• 1 \le N \le 2 \times 10^5
• 1 \le A_i \le 10^{18}
• 1 \le K \le 10^{18}
• All input values are integers.

Sample Input 1

3 3
1 2 3

Sample Output 1

3

For example, by choosing i = 1 twice and i = 2 once, the sequence becomes (3, 4, 3). In this case, the minimum value is 3.

It is impossible to make the minimum value 4 or greater, so output 3.

Sample Input 2

4 5
10 1 10 1

Sample Output 2

7

Sample Input 3

20 457
8 9 10 9 8 8 4 6 8 1 5 10 2 8 2 6 8 1 6 6

Sample Output 3

132

Problem Statement

There are N cells arranged in a horizontal row. The i-th cell from the left (1 \le i \le N) is called cell i.

There are M pieces of cloth. Laying cloth i (1 \le i \le M) covers cells L_i through R_i.

Answer Q queries. For the q-th query (1 \le q \le Q), integers S_q and T_q are given, so answer the following problem.

• Determine whether it is possible to choose exactly two pieces of cloth from the M pieces and lay them so that the following condition is satisfied.
  • Cells S_q through T_q are covered by at least one piece of cloth, and no other cells are covered by any cloth.

Constraints

• 1 \le N \le 2 \times 10^5
• 2 \le M \le 2 \times 10^5
• 1 \le L_i \le R_i \le N
• 1 \le Q \le 2 \times 10^5
• 1 \le S_q \le T_q \le N
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes
No
Yes
No

For the first query, the condition can be satisfied by choosing cloth 1 and cloth 3.

For the third query, the condition can be satisfied by choosing cloth 1 and cloth 2.

For the second and fourth queries, no choice of two pieces of cloth can satisfy the condition.

Sample Input 2

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

Sample Output 2

Yes
No
No
Yes
Yes
No
Yes
Yes
No
No

Problem Statement

You are given an integer N and an integer sequence D = (D_1, D_2, \ldots, D_{N-1}) of length N - 1.

Find the number, modulo 998244353, of permutations P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) that satisfy the following condition.

• For each 1 \le i \le N - 1, let P_a and P_b be the elements with the largest and the second largest values, respectively, among (P_i, P_{i+1}, \ldots, P_N); then |a - b| = D_i.

Constraints

• 2 \le N \le 2 \times 10^5
• 1 \le D_i \le N - i
• All input values are integers.

Sample Input 1

3
1 1

Sample Output 1

4

For example, we can verify that (2, 3, 1) satisfies the condition as follows.

• We have (P_1, P_2, P_3) = (2, 3, 1). The largest value is P_2 and the second largest value is P_1, and |2 - 1| = 1 = D_1.

• We have (P_2, P_3) = (3, 1). The largest value is P_2 and the second largest value is P_3, and |2 - 3| = 1 = D_2.

Four permutations satisfy the condition: (1, 2, 3), (1, 3, 2), (2, 3, 1), (3, 2, 1). Thus, output 4.

Sample Input 2

5
1 2 2 1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

70270200

Problem Statement

N apples fall on a number line. Apple i falls at coordinate X_i at time T_i.

You want to place some robots on the number line to collect all N apples. The robots can be placed at any coordinates.

Each robot starts operating from time 0 and can move freely along the number line at a speed of at most 1. Multiple robots may occupy the same coordinate at the same time. Each robot can collect apple i if and only if it is at coordinate X_i at time T_i.

Find the minimum number of robots needed to collect all apples.

Constraints

• 1 \le N \le 3 \times 10^5
• 0 \le T_i \le 3 \times 10^5
• 0 \le X_i \le 3 \times 10^5
• (T_i, X_i) \neq (T_j, X_j) (i \neq j)
• All input values are integers.

Sample Input 1

4
0 2
1 0
2 1
2 3

Sample Output 1

2

All apples can be collected with two robots by moving them as follows:

• Place robot 1 at coordinate 0 and robot 2 at coordinate 2.
• Time 0: Robot 2 collects apple 1.
• Time 1: Robot 1 collects apple 2. Move both robots in the positive direction at speed 1 until time 2.
• Time 2: Robot 1 collects apple 3 and robot 2 collects apple 4.

It is impossible to collect all apples with fewer than two robots, so output 2.

Sample Input 2

5
0 1
0 2
0 3
0 4
0 5

Sample Output 2

5

Sample Input 3

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

Sample Output 3

2