Problem Statement

There is a grid with H rows from top to bottom and W columns from left to right. Each square has a piece placed on it or is empty.

The state of the grid is represented by H strings S_1, S_2, \ldots, S_H, each of length W.
If the j-th character of S_i is #, the square at the i-th row from the top and j-th column from the left has a piece on it;
if the j-th character of S_i is ., the square at the i-th row from the top and j-th column from the left is empty.

How many squares in the grid have pieces on them?

Constraints

• 1\leq H,W \leq 10
• H and W are integers.
• S_i is a string of length W consisting of # and ..

Sample Input 1

3 5
#....
.....
.##..

Sample Output 1

3

The following three squares have pieces on them:

• the square at the 1-st row from the top and 1-st column from the left;
• the square at the 3-rd row from the top and 2-nd column from the left;
• the square at the 3-rd row from the top and 3-rd column from the left.

Thus, 3 should be printed.

Sample Input 2

1 10
..........

Sample Output 2

0

Since no square has a piece on it, 0 should be printed.

Sample Input 3

6 5
#.#.#
....#
..##.
####.
..#..
#####

Sample Output 3

16

Problem Statement

You are given a string S ending with er or ist.
If S ends with er, print er; if it ends with ist, print ist.

Constraints

• 2 \le |S| \le 20
• S consists of lowercase English letters.
• S ends with er or ist.

Sample Input 1

atcoder

Sample Output 1

er

S="atcoder" ends with er.

Sample Input 2

tourist

Sample Output 2

ist

Sample Input 3

er

Sample Output 3

er

Problem Statement

We have 4 cards with an integer 1 written on it, 4 cards with 2, \ldots, 4 cards with N, for a total of 4N cards.

Takahashi shuffled these cards, removed one of them, and gave you a pile of the remaining 4N-1 cards. The i-th card (1 \leq i \leq 4N - 1) of the pile has an integer A_i written on it.

Find the integer written on the card removed by Takahashi.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq N \, (1 \leq i \leq 4N - 1)
• For each k \, (1 \leq k \leq N), there are at most 4 indices i such that A_i = k.
• All values in input are integers.

Sample Input 1

3
1 3 2 3 3 2 2 1 1 1 2

Sample Output 1

3

Takahashi removed a card with 3 written on it.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

2

Problem Statement

There is a grid with H rows and W columns; initially, all cells are painted white. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

This grid is considered to be toroidal. That is, (i, 1) is to the right of (i, W) for each 1 \leq i \leq H, and (1, j) is below (H, j) for each 1 \leq j \leq W.

Takahashi is at (1, 1) and facing upwards. Print the color of each cell in the grid after Takahashi repeats the following operation N times.

• If the current cell is painted white, repaint it black, rotate 90^\circ clockwise, and move forward one cell in the direction he is facing. Otherwise, repaint the current cell white, rotate 90^\circ counterclockwise, and move forward one cell in the direction he is facing.

Constraints

• 1 \leq H, W \leq 100
• 1 \leq N \leq 1000
• All input values are integers.

Sample Input 1

3 4 5

Sample Output 1

.#..
##..
....

The cells of the grid change as follows due to the operations:

....   #...   ##..   ##..   ##..   .#..
.... → .... → .... → .#.. → ##.. → ##..
....   ....   ....   ....   ....   ....

Sample Input 2

2 2 1000

Sample Output 2

..
..

Sample Input 3

10 10 10

Sample Output 3

##........
##........
..........
..........
..........
..........
..........
..........
..........
#........#

Problem Statement

We have N boxes numbered 1 to N that are initially empty, and an unlimited number of blank cards.
Process Q queries in order. There are three kinds of queries as follows.

• 1 i j \colon Write the number i on a blank card and put it into box j.
• 2 i \colon Report all numbers written on the cards in box i, in ascending order.
• 3 i \colon Report all box numbers of the boxes that contain a card with the number i, in ascending order.

Here, note the following.

• In a query of the second kind, if box i contains multiple cards with the same number, that number should be printed the number of times equal to the number of those cards.
• In a query of the third kind, even if a box contains multiple cards with the number i, the box number of that box should be printed only once.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• For a query of the first kind:
  • 1 \leq i \leq 2 \times 10^5
  • 1 \leq j \leq N
• For a query of the second kind:
  • 1 \leq i \leq N
  • Box i contains some cards when this query is given.
• For a query of the third kind:
  • 1 \leq i \leq 2 \times 10^5
  • Some boxes contain a card with the number i when this query is given.
• At most 2 \times 10^5 numbers are to be reported.
• All values in the input are integers.

Sample Input 1

5
8
1 1 1
1 2 4
1 1 4
2 4
1 1 4
2 4
3 1
3 2

Sample Output 1

1 2
1 1 2
1 4
4

Let us process the queries in order.

• Write 1 on a card and put it into box 1.
• Write 2 on a card and put it into box 4.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1 and 2.
  • Print 1 and 2 in this order.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1, 1, and 2.
  • Note that you should print 1 twice.
• Boxes 1 and 4 contain a card with the number 1.
  • Note that you should print 4 only once, even though box 4 contains two cards with the number 1.
• Boxes 4 contains a card with the number 2.

Sample Input 2

1
5
1 1 1
1 2 1
1 200000 1
2 1
3 200000

Sample Output 2

1 2 200000
1

Problem Statement

We have a playlist with N songs numbered 1, \dots, N.
Song i lasts A_i seconds.

When the playlist is played, song 1, song 2, \ldots, and song N play in this order. When song N ends, the playlist repeats itself, starting from song 1 again. While a song is playing, the next song does not play; when a song ends, the next song starts immediately.

At exactly T seconds after the playlist starts playing, which song is playing? Also, how many seconds have passed since the start of that song?
There is no input where the playlist changes songs at exactly T seconds after it starts playing.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq T \leq 10^{18}
• 1 \leq A_i \leq 10^9
• The playlist does not change songs at exactly T seconds after it starts playing.
• All values in the input are integers.

Sample Input 1

3 600
180 240 120

Sample Output 1

1 60

When the playlist is played, the following happens. (Assume that it starts playing at time 0.)

• From time 0 to time 180, song 1 plays.
• From time 180 to time 420, song 2 plays.
• From time 420 to time 540, song 3 plays.
• From time 540 to time 720, song 1 plays.
• From time 720 to time 960, song 2 plays.
• \qquad\vdots

At time 600, song 1 is playing, and 60 seconds have passed since the start of that song.

Sample Input 2

3 281
94 94 94

Sample Output 2

3 93

Sample Input 3

10 5678912340
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

6 678912340

Problem Statement

There are N+Q points A_1,\dots,A_N,B_1,\dots,B_Q on a number line, where point A_i has a coordinate a_i and point B_j has a coordinate b_j.

For each j=1,2,\dots,Q, answer the following question:

• Let X be the point among A_1,A_2,\dots,A_N that is the k_j-th closest to point B_j. Find the distance between points X and B_j. More formally, let d_i be the distance between points A_i and B_j. Sort (d_1,d_2,\dots,d_N) in ascending order to get the sequence (d_1',d_2',\dots,d_N'). Find d_{k_j}'.

Constraints

• 1 \leq N, Q \leq 10^5
• -10^8 \leq a_i, b_j \leq 10^8
• 1 \leq k_j \leq N
• All input values are integers.

Sample Input 1

4 3
-3 -1 5 6
-2 3
2 1
10 4

Sample Output 1

7
3
13

Let us explain the first query.

The distances from points A_1, A_2, A_3, A_4 to point B_1 are 1, 1, 7, 8, respectively, so the 3rd closest to point B_1 is point A_3. Therefore, print the distance between point A_3 and point B_1, which is 7.

Sample Input 2

2 2
0 0
0 1
0 2

Sample Output 2

0
0

There may be multiple points with the same coordinates.

Sample Input 3

10 5
-84 -60 -41 -100 8 -8 -52 -62 -61 -76
-52 5
14 4
-2 6
46 2
26 7

Sample Output 3

11
66
59
54
88

Problem Statement

You are given a tree with NK vertices. The vertices are numbered 1,2,\dots,NK, and the i-th edge (i=1,2,\dots,NK-1) connects vertices u_i and v_i bidirectionally.

Determine whether this tree can be decomposed into N paths, each of length K. More precisely, determine whether there exists an N \times K matrix P satisfying the following:

• P_{1,1}, \dots, P_{1,K}, P_{2,1}, \dots, P_{N,K} is a permutation of 1,2,\dots,NK.
• For each i=1,2,\dots,N and j=1,2,\dots,K-1, there is an edge connecting vertices P_{i,j} and P_{i,j+1}.

Constraints

• 1 \leq N
• 1 \leq K
• NK \leq 2 \times 10^5
• 1 \leq u_i < v_i \leq NK
• The given graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

It can be decomposed into a path with vertices 1,2, a path with vertices 3,4, and a path with vertices 5,6.

Sample Input 2

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

Sample Output 2

No