Problem Statement

There are N people, labeled 1 to N. Person i has an integer A_i.

Among the people who satisfy the condition "None of the other N-1 people has the same integer as themselves," find the one with the greatest integer, and print that person's label.

If no person satisfies the condition, report that fact instead.

Constraints

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

Sample Input 1

9
2 9 9 7 9 2 4 5 8

Sample Output 1

9

Those who satisfy the condition are the persons labeled 4, 7, 8, and 9.
Their integers are 7, 4, 5, and 8, respectively, and the person with the largest integer is the person labeled 9.
Thus, the answer is 9.

Sample Input 2

4
1000000000 1000000000 998244353 998244353

Sample Output 2

-1

If no person satisfies the condition, print -1.

Problem Statement

You are given positive integers N and Q, and a string S of length N consisting of lowercase English letters.

Process Q queries. Each query is of one of the following two types.

• 1 x: Perform the following x times in a row: delete the last character of S and append it to the beginning.
• 2 x: Print the x-th character of S.

Constraints

• 2 \le N \le 5 \times 10^5
• 1 \le Q \le 5 \times 10^5
• 1 \le x \le N
• |S|=N
• S consists of lowercase English letters.
• At least one query in the format 2 x.
• N, Q, x are all integers.

Sample Input 1

3 3
abc
2 2
1 1
2 2

Sample Output 1

b
a

In the 1-st query, S is abc, so the 2-nd character b should be printed. In the 2-nd query, S is changed from abc to cab. In the 3-rd query, S is cab, so the 2-nd character a should be printed.

Sample Input 2

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

Sample Output 2

c
u
c
u

Problem Statement

Takahashi has many balls, on which nothing is written, and one bag. Initially, the bag is empty. Takahashi will do Q operations, each of which is of one of the following three types.

• Type 1: Write an integer X_i on a blank ball and put it in the bag.
• Type 2: For each ball in the bag, replace the integer written on it with that integer plus X_i.
• Type 3: Pick up the ball with the smallest integer in the bag (if there are multiple such balls, pick up one of them). Record the integer written on this ball and throw it away.

For each 1\leq i\leq Q, you are given the type P_i of the i-th operation and the value of X_i if the operation is of Type 1 or 2. Print the integers recorded in the operations of Type 3 in order.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 1 \leq P_i \leq 3
• 1 \leq X_i \leq 10^9
• All values in input are integers.
• There is one or more i such that P_i=3.
• If P_i=3, the bag contains at least one ball just before the i-th operation.

Sample Input 1

5
1 3
1 5
3
2 2
3

Sample Output 1

3
7

Takahashi will do the following operations.

• Write 3 on a ball and put it in the bag.
• Write 5 on a ball and put it in the bag.
• The bag now contains a ball with 3 and another with 5. Pick up the ball with the smaller of them, or 3. Record 3 and throw it away.
• The bag now contains just a ball with 5. Replace this integer with 5+2=7.
• The bag now contains just a ball with 7. Pick up this ball, record 7, and throw it away.

Therefore, we should print 3 and 7, in the order they are recorded.

Sample Input 2

6
1 1000000000
2 1000000000
2 1000000000
2 1000000000
2 1000000000
3

Sample Output 2

5000000000

Note that the outputs may not fit into a 32-bit integer.

Problem Statement

Find \displaystyle \sum_{k=0}^{10^{100}} \left \lfloor \frac{X}{10^k} \right \rfloor.

Notes

\lfloor A \rfloor denotes the value of A truncated to an integer.

Constraints

• X is an integer.
• 1 \le X < 10^{500000}

Sample Input 1

1225

Sample Output 1

1360

The value we seek is 1225+122+12+1+0+0+\dots+0=1360.

Sample Input 2

99999

Sample Output 2

111105

Beware of carries.

Sample Input 3

314159265358979323846264338327950288419716939937510

Sample Output 3

349065850398865915384738153697722542688574377708317

The values in input and output can both be enormous.

Problem Statement

In an N-dimensional space, the Manhattan distance d(x,y) between two points x=(x_1, x_2, \dots, x_N) and y = (y_1, y_2, \dots, y_N) is defined by:

A point x=(x_1, x_2, \dots, x_N) is said to be a lattice point if the components x_1, x_2, \dots, x_N are all integers.

You are given lattice points p=(p_1, p_2, \dots, p_N) and q = (q_1, q_2, \dots, q_N) in an N-dimensional space.
How many lattice points r satisfy d(p,r) \leq D and d(q,r) \leq D? Find the count modulo 998244353.

Constraints

• 1 \leq N \leq 100
• 0 \leq D \leq 1000
• -1000 \leq p_i, q_i \leq 1000
• All values in input are integers.

Sample Input 1

1 5
0
3

Sample Output 1

8

When N=1, we consider points in a one-dimensional space, that is, on a number line.
8 lattice points satisfy the conditions: -2,-1,0,1,2,3,4,5.

Sample Input 2

3 10
2 6 5
2 1 2

Sample Output 2

632

Sample Input 3

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

Sample Output 3

145428186