Problem Statement

There are N squares, indexed Square 1, Square 2, …, Square N, arranged in a row from left to right.
Also, there are K pieces. The i-th piece from the left is initially placed on Square A_i.
Now, we will perform Q operations against them. The i-th operation is as follows:

• If the L_i-th piece from the left is on its rightmost square, do nothing.
• Otherwise, move the L_i-th piece from the left one square right if there is no piece on the next square on the right; if there is, do nothing.

Print the index of the square on which the i-th piece from the left is after the Q operations have ended, for each i=1,2,\ldots,K.

Constraints

• 1\leq K\leq N\leq 200
• 1\leq A_1<A_2<\cdots<A_K\leq N
• 1\leq Q\leq 1000
• 1\leq L_i\leq K
• All values in input are integers.

Sample Input 1

5 3 5
1 3 4
3 3 1 1 2

Sample Output 1

2 4 5

At first, the pieces are on Squares 1, 3, and 4. The operations are performed against them as follows:

• The 3-rd piece from the left is on Square 4. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 3-rd piece from the left to Square 5. Now, the pieces are on Squares 1, 3, and 5.
• The 3-rd piece from the left is on Square 5. This is the rightmost square, so do nothing. The pieces are still on Squares 1, 3, and 5.
• The 1-st piece from the left is on Square 1. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 1-st piece from the left to Square 2. Now, the pieces are on Squares 2, 3, and 5.
• The 1-st piece from the left is on Square 2. This is not the rightmost square, but the next square on the right (Square 3) contains a piece, so do nothing. The pieces are still on Squares 2, 3, and 5.
• The 2-nd piece from the left is on Square 3. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 2-nd piece from the left to Square 4; Now, the pieces are still on Squares 2, 4, and 5.

Thus, after the Q operations have ended, the pieces are on Squares 2, 4, and 5, so 2, 4, and 5 should be printed in this order, with spaces in between.

Sample Input 2

2 2 2
1 2
1 2

Sample Output 2

1 2

Sample Input 3

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

Sample Output 3

2 5 6 7 9 10

Problem Statement

There is a simple undirected graph G with N vertices labeled with numbers 1, 2, \ldots, N.

You are given the adjacency matrix (A_{i,j}) of G. That is, G has an edge connecting vertices i and j if and only if A_{i,j} = 1.

For each i = 1, 2, \ldots, N, print the numbers of the vertices directly connected to vertex i in ascending order.

Here, vertices i and j are said to be directly connected if and only if there is an edge connecting vertices i and j.

Constraints

• 2 \leq N \leq 100
• A_{i,j} \in \lbrace 0,1 \rbrace
• A_{i,i} = 0
• A_{i,j} = A_{j,i}
• All input values are integers.

Sample Input 1

4
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0

Sample Output 1

2 3
1 4
1
2

Vertex 1 is directly connected to vertices 2 and 3. Thus, the first line should contain 2 and 3 in this order.

Similarly, the second line should contain 1 and 4 in this order, the third line should contain 1, and the fourth line should contain 2.

Sample Input 2

2
0 0
0 0

Sample Output 2

G may have no edges.

Sample Input 3

5
0 1 0 1 1
1 0 0 1 0
0 0 0 0 1
1 1 0 0 1
1 0 1 1 0

Sample Output 3

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

Problem Statement

You are given N strings S_1,S_2,\dots,S_N, each of length M, consisting of lowercase English letter. Here, S_i are pairwise distinct.

Determine if one can rearrange these strings to obtain a new sequence of strings T_1,T_2,\dots,T_N such that:

• for all integers i such that 1 \le i \le N-1, one can alter exactly one character of T_i to another lowercase English letter to make it equal to T_{i+1}.

Constraints

• 2 \le N \le 8
• 1 \le M \le 5
• S_i is a string of length M consisting of lowercase English letters. (1 \le i \le N)
• S_i are pairwise distinct.

Sample Input 1

4 4
bbed
abcd
abed
fbed

Sample Output 1

Yes

One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.

Sample Input 2

2 5
abcde
abced

Sample Output 2

No

No matter how the strings are rearranged, the condition is never satisfied.

Sample Input 3

8 4
fast
face
cast
race
fact
rice
nice
case

Sample Output 3

Yes

Problem Statement

There are zero or more sensors placed on a grid of H rows and W columns. Let (i, j) denote the square in the i-th row from the top and the j-th column from the left.
Whether each square contains a sensor is given by the strings S_1, S_2, \ldots, S_H, each of length W. (i, j) contains a sensor if and only if the j-th character of S_i is #.
These sensors interact with other sensors in the squares horizontally, vertically, or diagonally adjacent to them and operate as one sensor. Here, a cell (x, y) and a cell (x', y') are said to be horizontally, vertically, or diagonally adjacent if and only if \max(|x-x'|,|y-y'|) = 1.
Note that if sensor A interacts with sensor B and sensor A interacts with sensor C, then sensor B and sensor C also interact.

Considering the interacting sensors as one sensor, find the number of sensors on this grid.

Constraints

• 1 \leq H, W \leq 1000
• H and W are integers.
• S_i is a string of length W where each character is # or ..

Sample Input 1

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

Sample Output 1

3

When considering the interacting sensors as one sensor, the following three sensors exist:

• The interacting sensors at (1,2),(1,3),(2,4),(3,5),(3,6)
• The sensor at (4,1)
• The interacting sensors at (4,3),(5,3)

Sample Input 2

3 3
#.#
.#.
#.#

Sample Output 2

1

Sample Input 3

4 2
..
..
..
..

Sample Output 3

0

Sample Input 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

Sample Output 4

7

Problem Statement

N people, with ID numbers 1, 2, \dots, N, are lining up in front of a bank.
There will be Q events. The following three kinds of events can happen.

• 1 : The teller calls the person with the smallest ID number who has not been called.
• 2 x : The person with the ID number x comes to the teller for the first time. (Here, person x has already been called by the teller at least once.)
• 3 : The teller again calls the person with the smallest ID number who has already been called but has not come.

Print the ID numbers of the people called by the teller in events of the third kind.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 2 \leq Q \leq 5 \times 10^5
• There will not be an event of the first kind when all people have already been called at least once.
• For each event of the second kind, the person with the ID number x has already been called by the teller at least once.
• For each event of the second kind, the person with the ID number x will not come to the teller more than once.
• There will not be an event of the third kind when all people who have already been called have come to the teller.
• There is at least one event of the third kind.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1
2
4

For each i = 1, 2, \dots, Q, shown below is the set of people who have already been called but have not come just before the i-th event.

• i=1 : \lbrace \rbrace
• i=2 : \lbrace 1\rbrace
• i=3 : \lbrace 1,2\rbrace
• i=4 : \lbrace 1,2\rbrace
• i=5 : \lbrace 2\rbrace
• i=6 : \lbrace 2,3\rbrace
• i=7 : \lbrace 2\rbrace
• i=8 : \lbrace 2\rbrace
• i=9 : \lbrace 2,4\rbrace
• i=10 : \lbrace 4\rbrace

The events for i=3,7,10 are of the third kind, so you should print the persons with the smallest ID numbers in the sets for those events: 1, 2, 4.