Problem Statement

There is a device with a screen that shows a single-digit number, and a button.

When the screen is showing a number k, pressing the button once changes the number on the screen to a_k.

The device currently shows 0. After pressing the button 3 times, what will be shown on the screen?

Constraints

• 0\leq a_i \leq 9
• All values in input are integers.

Sample Input 1

9 0 1 2 3 4 5 6 7 8

Sample Output 1

7

The number on the screen transitions as 0 \rightarrow 9 \rightarrow 8 \rightarrow 7.

Sample Input 2

4 8 8 8 0 8 8 8 8 8

Sample Output 2

4

The number on the screen transitions as 0 \rightarrow 4 \rightarrow 0 \rightarrow 4.

Sample Input 3

0 0 0 0 0 0 0 0 0 0

Sample Output 3

0

Problem Statement

There is pasta consisting of N noodles at Takahashi's home. The length of the i-th noodle is A_i.
Takahashi has a meal plan for the next M days. On the i-th day, he is going to choose a pasta noodle of length exactly B_i and eat it. If no such noodle is available on any day, his plan fails. Additionally, he cannot eat the same noodle on multiple days.

Can Takahashi accomplish his meal plan?

Constraints

• 1 \leq M \leq N \leq 1000
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• All values in input are integers.

Sample Input 1

3 2
1 1 3
3 1

Sample Output 1

Yes

He can eat the 3-rd noodle on the 1-st day and the 1-st noodle on the 2-nd day, so his meal plan is feasible.

Sample Input 2

1 1
1000000000
1

Sample Output 2

No

A noodle of length exactly 1 is needed.

Sample Input 3

5 2
1 2 3 4 5
5 5

Sample Output 3

No

Since there are only 1 noodle of length 5, he cannot have a meal on the 2-nd day.

Problem Statement

There is a grid with N horizontal rows and N vertical columns, where each square is painted white or black.
The state of the grid is represented by N strings, S_i. If the j-th character of S_i is #, the square at the i-th row from the top and the j-th column from the left is painted black. If the character is ., then the square is painted white.

Takahashi can choose at most two of these squares that are painted white, and paint them black.
Determine if it is possible to make the grid contain 6 or more consecutive squares painted black aligned either vertically, horizontally, or diagonally.
Here, the grid is said to be containing 6 or more consecutive squares painted black aligned diagonally if the grid with N rows and N columns completely contains a subgrid with 6 rows and 6 columns such that all the squares on at least one of its diagonals are painted black.

Constraints

• 6 \leq N \leq 1000
• \lvert S_i\rvert =N
• S_i consists of # and ..

Sample Input 1

8
........
........
.#.##.#.
........
........
........
........
........

Sample Output 1

Yes

By painting the 3-rd and the 6-th squares from the left in the 3-rd row from the top, there will be 6 squares painted black aligned horizontally.

Sample Input 2

6
######
######
######
######
######
######

Sample Output 2

Yes

While Takahashi cannot choose a square to paint black, the grid already satisfies the condition.

Sample Input 3

10
..........
#..##.....
..........
..........
....#.....
....#.....
.#...#..#.
..........
..........
..........

Sample Output 3

No

Problem Statement

We have an empty sequence A.
Given Q queries, process them in order.
Each query is of one of the following three types.

• 1 x : Insert x to A.

• 2 x k : Among the elements of A that are less than or equal to x, print the k-th largest value. (k is no more than \bf{5})
  If there are less than k elements of A that are less than or equal to x, then print -1.

• 3 x k : Among the elements of A that are greater than or equal to x, print the k-th smallest value. (k is no more than \bf{5})
  If there are less than k elements of A that are greater than or equal to x, then print -1.

Constraints

• 1\leq Q \leq 2\times 10^5
• 1\leq x\leq 10^{18}
• 1\leq k\leq 5
• All values in input are integers.

Sample Input 1

11
1 20
1 10
1 30
1 20
3 15 1
3 15 2
3 15 3
3 15 4
2 100 5
1 1
2 100 5

Sample Output 1

20
20
30
-1
-1
1

After \text{query}_{1,2,3,4} have been processed, we have A=(20,10,30,20).

For \text{query}_{5,6,7}, the elements of A greater than or equal to 15 are (20,30,20).
The 1-st smallest value of them is 20; the 2-nd is 20; the 3-rd is 30.

Problem Statement

You are given a sequence A=(A_0,A_1,\ldots,A_{N-1}) of length N.
There is an initially empty dish. Takahashi is going to repeat the following operation K times.

• Let X be the number of candies on the dish. He puts A_{(X\bmod N)} more candies on the dish. Here, X\bmod N denotes the remainder when X is divided by N.

Find how many candies are on the dish after the K operations.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq K \leq 10^{12}
• 1 \leq A_i\leq 10^6
• All values in input are integers.

Sample Input 1

5 3
2 1 6 3 1

Sample Output 1

11

The number of candies on the dish transitions as follows.

• In the 1-st operation, we have X=0, so A_{(0\mod 5)}=A_0=2 more candies will be put on the dish.
• In the 2-nd operation, we have X=2, so A_{(2\mod 5)}=A_2=6 more candies will be put on the dish.
• In the 3-rd operation, we have X=8, so A_{(8\mod 5)}=A_3=3 more candies will be put on the dish.

Thus, after the 3 operations, there will be 11 candies on the dish. Note that you must not print the remainder divided by N.

Sample Input 2

10 1000000000000
260522 914575 436426 979445 648772 690081 933447 190629 703497 47202

Sample Output 2

826617499998784056

The answer may not fit into a 32-bit integer type.

Problem Statement

There is a skating rink represented by a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

The skating rink has N obstacles. The i-th obstacle is placed at (X_i,Y_i).

In a single move, Takahashi chooses one of the four directions, up, down, left, or right, and keeps moving until he hits an obstacle.
When he hits an obstacle, he stops at the square right before the obstacle. Since the skating rink is surrounded by cliffs, it is prohibited to start a move in which he will never hit an obstacle.

Takahashi is initially at (s_x,s_y). He wants to make some number of moves to stop at (g_x,g_y).

Find the minimum number of moves required to end up at (g_x, g_y). If it is not possible, report the fact.

Constraints

• 1\leq H \leq 10^9
• 1\leq W \leq 10^9
• 1\leq N \leq 10^5
• 1\leq s_x,g_x\leq H
• 1\leq s_y,g_y\leq W
• 1\leq X_i \leq H
• 1\leq Y_i \leq W
• (s_x,s_y)\neq (g_x,g_y)
• (s_x,s_y)\neq (X_i,Y_i)
• (g_x,g_y)\neq (X_i,Y_i)
• If i\neq j, then (X_i,Y_i)\neq (X_j,Y_j).
• All values in input are integers.

Sample Input 1

7 8 7
3 4
5 6
1 4
2 1
2 8
4 5
5 7
6 2
6 6

Sample Output 1

4

In the figure, (s_x,s_y) is denoted by S and (g_x,g_y) is denoted by G.
By moving as (3,4)\rightarrow(2,4) \rightarrow(2,2) \rightarrow(5,2) \rightarrow(5,6), he can end up at (g_x,g_y) with 4 moves.

Sample Input 2

4 6 2
3 2
3 5
4 5
2 5

Sample Output 2

-1

He must stop at (g_x,g_y).
Note that just passing through (g_x,g_y) is not considered to be ending up at the goal.

Sample Input 3

1 10 1
1 5
1 1
1 7

Sample Output 3

-1

If he chooses to move to the left, Takahashi will fall down the cliff after passing through (g_x,g_y).
Note that it is prohibited to start a move in which he will never hit an obstacle, as the skating rink is surrounded by cliffs.

Problem Statement

N players numbered 1 through N will participate in a round-robin tournament.
Specifically, for every pair (i,j) (1\leq i \lt j \leq N), Player i and Player j play a match against each other once, for a total of \frac{N(N-1)}{2} matches.
In every match, one of the players will be a winner and the other will be a loser; there is no draw.

M matches have already ended. In the i-th match, Player W_i won Player L_i.

List all the players who may become the unique winner after the round-robin tournament is completed.
A player is said to be the unique winner if the number of the player's wins is strictly greater than that of any other player.

Constraints

• 2\leq N \leq 50
• 0\leq M \leq \frac{N(N-1)}{2}
• 1\leq W_i,L_i\leq N
• W_i \neq L_i
• If i\neq j, then (W_i,L_i) \neq (W_j,L_j).
• (W_i,L_i) \neq (L_j,W_j)
• All values in input are integers.

Sample Input 1

4 2
2 1
2 3

Sample Output 1

2 4

Players 2 and 4 may become the unique winner, while Players 1 and 3 cannot.
Note that output like 4 2 is considered to be incorrect.

Sample Input 2

3 3
1 2
2 3
3 1

Sample Output 2

It is possible that no player can become the unique winner.

Sample Input 3

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

Sample Output 3

1 3 6 7

Problem Statement

There are some cards. Each card has one of N integers written on it. Specifically, there are B_i cards with A_i written on them.
Next, for a combination of M cards chosen out of these (B_1+B_2\cdots +B_N) cards, we define the score of the combination by the product of the integers written on the M cards.
Supposed that cards with the same integer written on them are indistinguishable, find the sum, modulo 998244353, of the scores over all possible combinations of M cards.

Constraints

• 1 \leq N \leq 16
• 1 \leq M \leq 10^{18}
• 1 \leq A_i < 998244353
• 1 \leq B_i \leq 10^{17}
• If i\neq j, then A_i \neq A_j.
• M\leq B_1+B_2+\cdots B_N
• All values in input are integers.

Sample Input 1

3 3
3 1
5 2
6 3

Sample Output 1

819

There are 6 possible combinations of 3 cards.

• A combination of 1 card with 3 written on it, and 2 cards with 5 written on them.
• A combination of 1 card with 3 written on it, 1 card with 5 written on it, and 1 card with 6 written on it.
• A combination of 1 card with 3 written on it, and 2 cards with 6 written on them.
• A combination of 2 cards with 5 written on them, and 1 card with 6 written on it.
• A combination of 1 card with 5 written on it, and 2 cards with 6 written on them.
• A combination of 3 cards with 6 written on them.

The scores are 75, 90, 108, 150, 180, and 216, respectively, for a sum of 819.

Sample Input 2

3 2
1 1
5 2
25 1

Sample Output 2

180

"A combination of a card with 1 and another card with 25" and "a combination of two cards with 5 written on them" have the same score of 25, but they are considered to be different combinations.

Sample Input 3

10 232657150901347497
139547946 28316250877914575
682142538 78223540024979445
110643588 74859962623690081
173455495 60713016476190629
271056265 85335723211047202
801329567 48049062628894325
864844366 54979173822804784
338794337 69587449430302156
737638908 15812229161735902
462149872 49993004923078537

Sample Output 3

39761306

Be sure to print the answer modulo 998244353.