Problem Statement

N players with ID numbers 1, 2, \ldots, N are playing a card game.
Each player plays one card.

Each card has two parameters: color and rank, both of which are represented by positive integers.
For i = 1, 2, \ldots, N, the card played by player i has a color C_i and a rank R_i. All of R_1, R_2, \ldots, R_N are different.

Among the N players, one winner is decided as follows.

• If one or more cards with the color T are played, the player who has played the card with the greatest rank among those cards is the winner.
• If no card with the color T is played, the player who has played the card with the greatest rank among the cards with the color of the card played by player 1 is the winner. (Note that player 1 may win.)

Print the ID number of the winner.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq T \leq 10^9
• 1 \leq C_i \leq 10^9
• 1 \leq R_i \leq 10^9
• i \neq j \implies R_i \neq R_j
• All values in the input are integers.

Sample Input 1

4 2
1 2 1 2
6 3 4 5

Sample Output 1

4

Cards with the color 2 are played. Thus, the winner is player 4, who has played the card with the greatest rank, 5, among those cards.

Sample Input 2

4 2
1 3 1 4
6 3 4 5

Sample Output 2

1

No card with the color 2 is played. Thus, the winner is player 1, who has played the card with the greatest rank, 6, among the cards with the color of the card played by player 1 (color 1).

Sample Input 3

2 1000000000
1000000000 1
1 1000000000

Sample Output 3

1

Problem Statement

You are given an integer N and a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

Given Q queries, process them in the given order. Each query is of one of the following two kinds:

• 1 k x : set the value A _ k to x.
• 2 k : print the value A _ k.

Constraints

• 1 \leq N \leq 10 ^ 5
• 1 \leq Q \leq 10 ^ 5
• 0 \leq A _ i \leq 10 ^ 9\ (1\leq i\leq N)
• 1\leq k\leq N for all queries.
• 0\leq x\leq 10 ^ 9 for all queries of the first kind.
• There is at least one query of the second kind.
• All values in the input are integers.

Sample Input 1

3
1 3 5
7
2 2
2 3
1 3 0
2 3
1 2 8
2 2
2 1

Sample Output 1

3
5
0
8
1

Initially, A=(1,3,5).

• For the 1-st query, A=(1,3,5), where A _ 2=3, so 3 should be printed.
• For the 2-nd query, A=(1,3,5), where A _ 3=5, so 5 should be printed.
• The 3-rd query sets the value A _ 3 to 0, making A=(1,3,0).
• For the 4-th query, A=(1,3,0), where A _ 3=0, so 0 should be printed.
• The 5-th query sets the value A _ 2 to 8, making A=(1,8,0).
• For the 6-th query, A=(1,8,0), where A _ 2=8, so 8 should be printed.
• For the 7-th query, A=(1,8,0), where A _ 1=1, so 1 should be printed.

Sample Input 2

5
22 2 16 7 30
10
1 4 0
1 5 0
2 2
2 3
2 4
2 5
1 4 100
1 5 100
2 3
2 4

Sample Output 2

2
16
0
0
16
100

Sample Input 3

7
478 369 466 343 541 42 165
20
2 1
1 7 729
1 6 61
1 6 838
1 3 319
1 4 317
2 4
1 1 673
1 3 176
1 5 250
1 1 468
2 6
1 7 478
1 5 595
2 6
1 6 599
1 6 505
2 3
2 5
2 1

Sample Output 3

478
317
838
838
176
595
468

Problem Statement

There is a class with N students. The height of the i-th student (1 \leq i \leq N) is A_i.

For each j=1,2,\ldots,Q, answer the following question.

• How many of the N students have a height of at least x_j?

Constraints

• 1 \leq N,Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq x_j \leq 10^9
• All values in input are integers.

Sample Input 1

3 1
100 160 130
120

Sample Output 1

2

The students with a height of at least 120 are the 2-nd and 3-rd ones.

Sample Input 2

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

Sample Output 2

0
1
2
3
4

Sample Input 3

5 5
804289384 846930887 681692778 714636916 957747794
424238336
719885387
649760493
596516650
189641422

Sample Output 3

5
3
5
5
5

Problem Statement

How many integer sequences of length N, A=(A_1, \ldots, A_N), satisfy all of the conditions below?

• 1\le A_i \le M (1 \le i \le N)

• \displaystyle\sum _{i=1}^N A_i \leq K

Since the count can get enormous, find it modulo 998244353.

Constraints

• 1 \leq N, M \leq 50
• N \leq K \leq NM
• All values in input are integers.

Sample Input 1

2 3 4

Sample Output 1

6

The following six sequences satisfy the conditions.

• (1,1)
• (1,2)
• (1,3)
• (2,1)
• (2,2)
• (3,1)

Sample Input 2

31 41 592

Sample Output 2

798416518

Be sure to print the count modulo 998244353.

Problem Statement

Takahashi and Aoki will play a game of taking stones using a sequence (A_1, \ldots, A_K).

There is a pile that initially contains N stones. The two players will alternately perform the following operation, with Takahashi going first.

• Choose an A_i that is at most the current number of stones in the pile. Remove A_i stones from the pile.

The game ends when the pile has no stones.

If both players attempt to maximize the total number of stones they remove before the end of the game, how many stones will Takahashi remove?

Constraints

• 1 \leq N \leq 10^4
• 1 \leq K \leq 100
• 1 = A_1 < A_2 < \ldots < A_K \leq N
• All values in the input are integers.

Sample Input 1

10 2
1 4

Sample Output 1

5

Below is one possible progression of the game.

• Takahashi removes 4 stones from the pile.
• Aoki removes 4 stones from the pile.
• Takahashi removes 1 stone from the pile.
• Aoki removes 1 stone from the pile.

In this case, Takahashi removes 5 stones. There is no way for him to remove 6 or more stones, so this is the maximum.

Below is another possible progression of the game where Takahashi removes 5 stones.

• Takahashi removes 1 stone from the pile.
• Aoki removes 4 stones from the pile.
• Takahashi removes 4 stones from the pile.
• Aoki removes 1 stone from the pile.

Sample Input 2

11 4
1 2 3 6

Sample Output 2

8

Below is one possible progression of the game.

• Takahashi removes 6 stones.
• Aoki removes 3 stones.
• Takahashi removes 2 stones.

In this case, Takahashi removes 8 stones. There is no way for him to remove 9 or more stones, so this is the maximum.

Sample Input 3

10000 10
1 2 4 8 16 32 64 128 256 512

Sample Output 3

5136