Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You are given two strings s and t of length 3 consisting of only lowercase and uppercase English letters.

If the strings s and t are completely equal despite we distinguish letter case (i.e. lowercase and uppercase), print same; if they can read the same if we remove the distinction of letter case, print case-insensitive; otherwise, print different.

Constraints

• The strings s and t have length 3 and contain only lowercase and uppercase English letters.

Sample Input 1

AbC
ABc

Sample Output 1

case-insensitive

• Since AbC and ABc can read the same if we treat the uppercase and lowercase letters as equivalent, print case-insensitive.

Sample Input 2

xyz
xyz

Sample Output 2

same

• Since s and t are completely the same strings as xyz, print same.

Sample Input 3

aDs
kjH

Sample Output 3

different

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Contest

We will hold a programming contest. There will be N participants and M problems in this contest. The participants are numbered 1,2,\ldots,N, and the problems are numbered 1,2,\ldots,M.

In this contest, the score for a problem will depend on the number of participants who solve that problem. More specifically, the score is N - \text{(the number of participants who have solved the problem at the moment)}.

The score of a participant is the sum of the scores for the problems solved by that participant. Note that a change in the score for a problem will also change the score of participants. For example, in the case N=2 and M=1, the score for Problem 1 is initially 2. If Participant 1 solves Problem 1, the score for Problem 1 becomes 1, and his score also becomes 1. If Participant 2 then solves Problem 1, the score for Problem 2 becomes 0, and the score of Participant 1 and 2 both become 0.

Process Q queries s_1, s_2, \ldots, s_Q in order, which will be given in the formats below:

• Print the current score of Participant n. This query is given in the format 1 n.
• It is reported that Participant n solves Problem m. This query is given in the format 2 n m.

Constraints

• 1 \leq N, Q \leq 10^5
• 1 \leq M \leq 50
• s_i is a string in one of the following formats:
  • 1 n (1 \leq n \leq N)
  • 2 n m (1 \leq n \leq N, 1 \leq m \leq M)
    • No participant solves the same problem multiple times.

Sample Input 1

2 1 6
2 1 1
1 1
1 2
2 2 1
1 1
1 2

Sample Output 1

1
0
0
0

• Initially, the score for Problem 1 is 2, and the score of Participant 1 and 2 are both 0.
• After Participant 1 solves Problem 1 in the first query, the score for Problem 1 becomes 1, and the score of Participant 1 and 2 becomes 1 and 0, respectively.
• In the second query, the score of Participant 1 - which is 1 - is printed.
• In the third query, the score of Participant 2 - which is 0 - is printed.
• After Participant 2 solves Problem 1 in the fourth query, the score for Problem 1 becomes 0, and the score of Participant 1 and 2 both become 0.
• In the fifth query, the score of Participant 1 - which is 0 - is printed.
• In the sixth query, the score of Participant 2 - which is 0 - is printed.

Sample Input 2

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

Sample Output 2

0
4
3
0
3
10
9
4
4
4
0
0
9
3
9
0
3

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Consider the N-th term of a geometric sequence with the initial value of A and the common ratio of R. If it is greater than 10^9, print large; otherwise, print its value as an integer.

Constraints

• All values in input are integers.
• 1 \leq A, R, N \leq 10^9

Sample Input 1

2 3 4

Sample Output 1

54

The geometric sequence with the initial value of 2 and the common ratio of 3 is: 2, 6, 18, 54, \ldots. Its fourth term is 54, so we should print 54.

Sample Input 2

4 3 21

Sample Output 2

large

The 21-st term of a geometric sequence with the initial value of 4 and the common ratio of 3 is 13947137604, which is greater than 10^9. Thus, we should print large.

Sample Input 3

12 34 5

Sample Output 3

16036032

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have an electric bulletin board that shows an N-digit number. The board is made of a grid of lamps with 5 rows and 4N+1 columns. For each j such that 1 \leq j \leq N, the j-th digit from the left is displayed using the lamps in the (4j-2)-th, (4j-1)-th, and (4j)-th columns from the left. All the remaining lamps in the 1-st, 5-th, \ldots, (4N+1)-th columns are off.

The state of the board is represented by five strings of length 4N+1 each: s_1, s_2, s_3, s_4, and s_5. More specifically, for each pair (i,j) such that 1 \leq i \leq 5 and 1 \leq j \leq 4N+1, the j-th character of s_{i} repsesents the state of the lamp at the i-th row from the top and the j-th column from the left.

The characters # and . stand for "on" and "off" states, respectively.

Print the sequence of digits displayed on the board.

To see how the board displays each digit, refer to Sample Input 1.

Constraints

• 1 \leq N \leq 50
• s_1, s_2, s_3, s_4, and s_5 are strings of length 4N+1 each and consist of # and ..
• The 1-st, 5-th, \ldots, (4N+1)-th characters of each of the strings s_1, s_2, s_3, s_4, and s_5 are all .s.
• The input is a valid representation of a sequence of digits in the same way as in Sample Input 1.

Sample Input 1

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

Sample Output 1

0123456789

Sample Input 2

29
.###.###.###.###.###.###.###.###.###.#.#.###.#.#.#.#.#.#.###.###.###.###..#..###.###.###.###.###.#.#.###.###.###.###.
...#.#.#...#.#.#.#.#.#...#.#...#.#.#.#.#.#...#.#.#.#.#.#.#.....#.#.#.#.#.##..#.#...#.#.#...#.#...#.#...#.#.....#...#.
.###.#.#...#.###.#.#.###.###...#.###.###.###.###.###.###.###...#.###.#.#..#..###...#.###.###.###.###.###.###.###.###.
.#...#.#...#...#.#.#.#.#...#...#.#.#...#.#.#...#...#...#.#.#...#...#.#.#..#..#.#...#...#.#...#.#...#.#.....#...#.#...
.###.###...#.###.###.###.###...#.###...#.###...#...#...#.###...#.###.###.###.###...#.###.###.###...#.###.###.###.###.

Sample Output 2

20790697846444679018792642532

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is an undirected graph with N vertices numbered 1,2,3,\ldots,N and M edges numbered 1,2,3,\ldots,M. Edge i connects Vertex u_i and v_i bidirectionally.

Each vertex can be painted in a color. Initially, Vertex i is painted in Color c_i. (In this problem, colors are represented by integers from 1 through 10^5.)

Each vertex has a sprinkler on it. When the sprinkler at Vertex i is activated, it will repaint all the vertices adjacent to Vertex i in the color of Vertex i when it is activated.

Process Q queries s_1, s_2, \ldots, s_Q in order, which will be given in the formats below:

• Print the current color of Vertex x, and then activate the sprinkler on Vertex x. This query is given in the format 1 x.
• Print the current color of Vertex x, and then overwrite the color of Vertex x to y. This query is given in the format 2 x y.

Constraints

• All values in input are integers.
• 1 \leq N,Q \leq 200
• 0 \leq M \leq N(N-1)/2
• 1 \leq u_i, v_i\leq N
• 1 \leq c_i\leq 10^5
• s_i is a string in one of the following formats:
  • 1 x (1 \leq x \leq N)
  • 2 x y (1 \leq x \leq N, 1 \leq y \leq 10^{5})
• The given graph contains no multiple edges or self-loops.

Sample Input 1

3 2 3
1 2
2 3
5 10 15
1 2
2 1 20
1 1

Sample Output 1

10
10
20

• Initially, Vertex 1, 2, and 3 are painted in Color 5, 10, and 15, respectively.
• The first query repaints all the vertices adjacent to Vertex 2 in Color 10. After that, Vertex 1, 2 and 3 are all painted in Color 10.
• The second query overwrites the color of Vertex 1 to Color 20.
• The third query repaints all the vertices adjacent to Vertex 2 in Color 20.

Sample Input 2

30 10 20
11 13
30 14
6 4
7 23
30 8
17 4
6 23
24 18
26 25
9 3
18 4 36 46 28 16 34 19 37 23 25 7 24 16 17 41 24 38 6 29 10 33 38 25 47 8 13 8 42 40
2 1 9
1 8
1 9
2 20 24
2 26 18
1 20
1 26
2 24 31
1 4
2 21 27
1 25
1 29
2 10 14
2 2 19
2 15 36
2 28 6
2 13 5
1 12
1 11
2 14 43

Sample Output 2

18
19
37
29
8
24
18
25
46
10
18
42
23
4
17
8
24
7
25
16

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given an integer N and a matrix a of size N×N consisting of lowercase English letters. Your task is to construct a string S of length N that satisfies the following conditions:

• The string S contains only lowercase English letters.
• The string S is a palindrome. Recall that a string is called a palindrome if it reads the same way in both directions.
• Every character S_{i} equals at least one of the characters a_{i,1},a_{i,2}, \ldots, a_{i,N}.

If no strings can satisfy all the above conditions, you have to point out this fact.

Constraints

• N is an integer.
• 1 \leq N \leq 500
• Each character a_{i,j} is a lowercase English letter.

Sample Input 1

2
yc
ys

Sample Output 1

yy

Sample Input 2

2
rv
jh

Sample Output 2

-1

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have an infinite two-dimensional grid. Snuke is initially standing at the square (0,0) in this grid. There are N squares that contain an obstacle, and Snuke cannot enter those squares. The i-th obstacle is at the square (x_i, y_i). When Snuke is at the square (x, y), he can get to one of the following six squares in one move:

• (x+1, y+1)
• (x, y+1)
• (x-1, y+1)
• (x+1, y)
• (x-1, y)
• (x, y-1)

Print the minimum number of moves Snuke needs to reach the square (X, Y). If this square is unreachable, print -1.

Constraints

• All values in input are integers.
• 1 \leq N \leq 800
• -200 \leq x_i, y_i, X, Y \leq 200
• The pairs (x_i, y_i) are distinct. That is, no square contains two or more obstacles.
• The squares (0, 0) and (X, Y) do not contain an obstacle.
• (X, Y) \neq (0, 0)

Sample Input 1

1 2 2
1 1

Sample Output 1

3

Shown below is a part of the grid:

..G
.#.
S..

Here, S, G, and # stand for the square (0, 0), (X, Y) = (2, 2), and a square with an obstacle.

The minimum number of moves needed to reach (X, Y) = (2, 2) is three. One way to achieve it is (0, 0) \to (0, 1) \to (1, 2) \to (2, 2).

Sample Input 2

1 2 2
2 1

Sample Output 2

2

Sample Input 3

5 -2 3
1 1
-1 1
0 1
-2 1
-3 1

Sample Output 3

6

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Snuke will run the hurdles on a number line. He will start at coordinate 0 and finish at coordinate L. There are N hurdles on the number line, and the i-th hurdle from the left is at coordinate x_i. (0 < x_1 < x_2 < \cdots < x_N < L holds.)

Snuke can repeatedly choose one of the three actions below and do it:

• Action 1: Run the distance of 1.
• Action 2: Run the distance of 0.5, jump the distance of 1, and run the distance of 0.5, for a total distance of 2.
• Action 3: Run the distance of 0.5, jump the distance of 3, and run the distance of 0.5, for a total distance of 4.

Snuke goes at the speed of 1 unit distance per T_1 seconds while running, and 1 unit distance per T_2 seconds while in the air. However, if Snuke is at coordinate x while he is not in the air and there is a hurdle at coordinate x, it takes extra T_3 seconds to go past the point. Here, T_1, T_2, and T_3 are even numbers.

Find the minimum number of seconds Snuke needs before he passes coordinate L. (If he jumps over coordinate L, we consider the time when he passes coordinate L in the air.) We can prove that the answer is an integer.

Constraints

• All values in input are integers.
• 2 \leq L \leq 10^5
• 1 \leq N < L
• 0 < x_1 < x_2 < \cdots < x_N < L
• 2 \leq T_1, T_2, T_3\leq 1000
• T_1, T_2, and T_3 are even numbers.

Sample Input 1

2 5
1 4
2 2 20

Sample Output 1

10

There are hurdles at coordinate 1 and 4. In this case, the optimal strategy is as follows:

1. Do Action 2. We run the distance of 1 in total and jump the distance of 1, so it takes 2 \times 1 + 2 \times 1 = 4 seconds in total.
2. Do Action 1. It takes 2 seconds.
3. Do Action 3, during which we pass coordinate L=5. Before we pass this point, we run the distance of 0.5 and jump the distance of 1.5, so it takes 2 \times 0.5 + 2 \times 1.5 = 4 seconds in total.

The time taken in this optimal strategy is 4 + 2 + 4 = 10 seconds in total, so we should print 10.

Sample Input 2

4 5
1 2 3 4
2 20 100

Sample Output 2

164

Sample Input 3

10 19
1 3 4 5 7 8 10 13 15 17
2 1000 10

Sample Output 3

138

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You have a matrix a of size N \times N satisfying the following condition:

• a_{i,j} = N \times (i - 1) + j - 1 ( 1 \leq i,j \leq N )

You are given Q queries. Your task is to process them sequentially.

Each query Query_{1}, Query_{2} \cdots Query_{Q} is represented by one of the following four types of format:

• 1 A B : Swap all the elements of the A-th row and the B-th row of the matrix a without changing their column numbers.
• 2 A B : Swap all the elements of the A-th column and the B-th column of the matrix a without changing their row numbers.
• 3 : Transpose the matrix a, i.e. the element of a_{i,j} will appear at a_{j,i} after performing this query.
• 4 A B : Output the element of a_{i,j}, i.e. output the element located at the intersection of the A-th row and the B-th column of the matrix a.

Note that the matrix a will remain the same if the given queries are of format either 1 A B or 2 A B and A=B.

Constraints

• All the values in the input are integers.
• 1 \leq N, Q \leq 10^{5}
• 1 \leq A, B \leq N
• It is guaranteed that there is at least one query of format 4 A B in the input.

Sample Input 1

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

Sample Output 1

0
1
2
3
0
2
1
3
1
3
0
2
3
1
2
0

In the sample 1, you can check all the elements of the matrix a after performing each type of query.

Sample Input 2

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

Sample Output 2

1
6
8

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

N children, who have never had sushi, have come to a sushi-go-round. The children are numbered 1,2,3,\ldots,N.

The conveyer belt will convey M sushi plates one by one. The deliciousness of the i-th plate is a_i. The plates will pass in front of Child 1, 2, 3, \ldots, N, in this order.

When a plate is passing in front of a child, he/she will pick up the plate and eat it if and only if one of the following conditions is satisfied:

• He/she has never had a plate.
• The deliciousness of the plate is greater than those of all plates he/she has had so far.

For each plate, find which child will have it.

Constraints

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

Sample Input 1

2 5
5 3 2 4 8

Sample Output 1

1
2
-1
2
1

• First, the conveyer belt conveys a plate with the deliciousness of 5.
  • When the plate is passing in front of Child 1, he has never had a plate, so he gets it.
• Second, the conveyer belt conveys a plate with the deliciousness of 3.
  • When the plate is passing in front of Child 1, its deliciousness is not greater than that of the plate he has had, so he ignores it.
  • When the plate is passing in front of Child 2, she has never had a plate, so she gets it.
• Third, the conveyer belt conveys a plate with the deliciousness of 2.
  • When the plate is passing in front of Child 1, its deliciousness is not greater than those of the plates he has had, so he ignores it.
  • When the plate is passing in front of Child 2, its deliciousness is not greater than those of the plates she has had, so she ignores it.
  • When the plate is passing in front of Child 3, he has never had a plate, so he gets this plate.
• Fourth, the conveyer belt conveys a plate with the deliciousness of 4.
  • When the plate is passing in front of Child 1, its deliciousness is not greater than those of the plates he has had, so he ignores it.
  • When the plate is passing in front of Child 2, its deliciousness is greater than those of the plates she has had, so she gets it.
• Fifth, the conveyer belt conveys a plate with the deliciousness of 8.
  • When the plate is passing in front of Child 1, its deliciousness is greater than those of the plates he has had, so he gets it.

Sample Input 2

5 10
13 16 6 15 10 18 13 17 11 3

Sample Output 2

1
1
2
2
3
1
3
2
4
5

Sample Input 3

10 30
35 23 43 33 38 25 22 39 22 6 41 1 15 41 3 20 50 17 25 14 1 22 5 10 34 38 1 12 15 1

Sample Output 3

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

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have N desks numbered 1,2,\ldots,N, and N containers numbered 1,2,\ldots,N. We can pile multiple containers on a desk.

Initially, Container i is placed on Desk i.

We will ask you to process Q queries in order. In the i-th query, move Container x_i and the containers above it from Desk f_i to Desk t_i, without changing the order they are piled in.

Here, if there are already some containers on Desk t_i, place Container x_i on top of the containers on Desk t_i. See the figure below:

• In this example, f=1,t=2,x=4. We are moving Container 4 and the container above it - Container 2 - from Desk 1 to Desk 2.
• Since there are already some containers - Container 3 and 5 - on Desk 2, so we place Container 4 on top of them.

After processing the Q queries, find the desk on which each container lies.

Constraints

• All values in input are integers.
• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq f_i, t_i, x_i\leq N
• f_i \neq t_i
• Container x_i is guaranteed to be placed on Desk f_i when the query is given.

Sample Input 1

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

Sample Output 1

3
3
1

• In the first query, we move Container 1 from Desk 1 to Desk 2. Container 2 is already on Desk 2, so we place Container 1 on top of it.
• In the second query, we move Container 2 and the container above it - Container 1 - from Desk 2 to Desk 3. Container 3 is already on Desk 3, so we place Container 2 and 1 on top of it.
• In the third query, we move Container 3 and the containers above it - Container 2 and 1 - from Desk 2 to Desk 1.
• In the fourth query, we move Container 2 and the container above it - Container 1 - from Desk 1 to Desk 3.
• In the end, Container 1 and 2 lie on Desk 3, and Container 3 lies on Desk 1.

Sample Input 2

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

Sample Output 2

7
3
7
7
5
9
7
7
10
7

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Takahashi's grocery store has a display rack. The rack has N sections numbered 1 to N, each of which contains a queue of products. In Section i, K_i products line up from front to back, and the expiry date of the j-th product from the front is T_{i,j}.

Here, it is guaranteed that all the products have distinct expiry dates.

M customers will visit the store one by one. The i-th customer will check the frontmost a_i products for every section. (If a section has less than a_i products, he/she will check all those products.) Then, he/she will pick up the product with the greatest value of the expiry date among the products checked, and buy it.

For each of the customers, find the expiry date of the product he/she will buy.

Constraints

• All values in input are integers.
• 1 \leq N \leq 10^5
• 1 \leq K_i \leq 10^5
• 1 \leq M \leq \sum_{i=1}^{N}K_i \leq 3 \times 10^5
• 1 \leq T_{i,j} \leq 10^9
• T_{i,j} are distinct.
• 1 \leq a_i \leq 2

Sample Input 1

2
3 1 200 1000
5 20 30 40 50 2
5
1 1 1 2 2

Sample Output 1

20
30
40
200
1000

• The expiry dates of the frontmost products in Section 1 and 2 are now 1 and 20, respectively. Among them, 20 is greater, so the first customer will buy that product.
• The expiry dates of the frontmost products in Section 1 and 2 are now 1 and 30, respectively. Among them, 30 is greater, so the second customer will buy that product.
• The expiry dates of the frontmost products in Section 1 and 2 are now 1 and 40, respectively. Among them, 40 is greater, so the third customer will buy that product.
• The expiry dates of the frontmost products in Section 1 and 2 are now 1 and 50, respectively, and the expiry dates of the second frontmost products in Section 1 and 2 are now 200 and 2, respectively. Among these values, 200 is the greatest, so the fourth customer will buy that product.
• The expiry dates of the frontmost products in Section 1 and 2 are now 1 and 50, respectively, and the expiry dates of the second frontmost products in Section 1 and 2 are now 1000 and 2, respectively. Among these values, 1000 is the greatest, so the fifth customer will buy that product.

Sample Input 2

10
6 8 24 47 29 73 13
1 4
5 72 15 68 49 16
5 65 20 93 64 91
6 100 88 63 50 90 44
2 6 1
10 14 2 76 28 21 78 43 11 97 70
5 31 9 62 84 40
8 10 46 96 23 98 19 38 51
2 37 77
20
1 1 1 1 2 2 2 1 1 2 2 2 2 2 1 2 1 2 2 1

Sample Output 2

100
88
72
65
93
77
68
63
50
90
64
91
49
46
44
96
37
31
62
20

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

The Kingdom of Soonuke has N towns.

There are M roads in the kingdom. The i-th road connects Town u_i and v_i bidirectionally. You need to pay the toll of 1 yen each time you use a road. We know that any town can be reached from any town by using some number of roads.

Takaaha, a merchant, is now at Town s and wants to make transactions in K towns t_1, t_2, \ldots, t_K

What is the minimum total toll Takaaha needs to pay when he starts at Town s and visit each of the K towns at least once? He does not need to come back to Town s in the end.

Note that using the same road multiple times will cost you the toll that number of times.

Constraints

• All values in input are integers.
• 2 \leq N \leq 10^5
• N - 1 \leq M \leq 10^5
• 1 \leq u_i < v_i \leq N
• If i \neq j, (u_i, v_i) \neq (u_j, v_j).
• 1 \leq s \leq N
• 1 \leq K \leq \min (N - 1, 16)
• 1 \leq t_i \leq N
• If i \neq j, t_i \neq t_j.
• s \neq t_i

Sample Input 1

3 2
1 2
2 3
2
2
1 3

Sample Output 1

3

If we go from Town 2 to Town 1, then go back to Town 2, then go to Town 3, we can visit the towns 1 and 3 with the total toll of 3 yen.

Sample Input 2

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

Sample Output 2

4

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have a sequence of length N: a_1, a_2, \ldots, a_N. Initially, a_i = i.

You will be given Q queries regarding this sequence.

The i-th query will be described by three integers t_i, x_i, and y_i, as follows:

• if t_i = 1, swap a_{x_i} and a_{x_i + 1};
• if t_i = 2, rearrange a_{x_i}, a_{x_i + 1}, \ldots a_{y_i} in ascending order.

Print the sequence a after all the queries are processed in order.

Constraints

• All values in input are integers.
• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• t_i is 1 or 2.
• If t_i = 1, then 1 \leq x_i < N and y_i = 0.
• If t_i = 2, then 1 \leq x_i < y_i \leq N.

Sample Input 1

5 3
1 1 0
1 2 0
2 2 4

Sample Output 1

2 1 3 4 5

• After the first query is processed, a is 2, 1, 3, 4, 5.
• After the second query is processed, a is 2, 3, 1, 4, 5.
• After the third query is processed, a is 2, 1, 3, 4, 5.

Sample Input 2

10 15
1 3 0
1 5 0
1 4 0
1 2 0
1 3 0
2 4 7
1 5 0
1 7 0
1 9 0
1 8 0
2 3 5
1 8 0
1 9 0
1 5 0
1 2 0

Sample Output 2

1 2 4 5 3 6 8 7 9 10

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You are playing a quoits game with N pins numbered from 1 to N.

The game is divided into three rounds, round 1, round 2, and round 3. In each round, you will hit exactly M distinct pins by throwing hoops. You have to throw all the hoops, and the hoops you have made encircle the pins (i.e. hit) in each round will remain in that place until the game ends.

If you hit the pin j in the round i, you will gain (A_{j} \times (B_{j})^{i} \mod R_{i}) points.

However, having the same pins encircled by many hoops is not exciting. In order to encourage the uniformity of the number of hits for each pin, you get another rule: after the game is over, if the pin j is being encircled by a positive number of hoops, in particular, by i hoops, then you will lose A_{j} \times (B_{j}) ^{i} points. Thus, your total points might be negative.

You want to maximize the total points you can get by wisely deciding which set of pins you will hit in each round.

Constraints

• All the values in the input are integers.
• 1 \leq M \leq N \leq 500
• 2 \leq A_{i}, B_{i} \leq 1000
• 2 \leq R_{1}, R_{2}, R_{3} \leq 10^{5}

Sample Input 1

2 1
3 2
3 3
100000 100000 100000

Sample Output 1

81

In each round, if you hit the pin 1, you will gain 9, 27, 81 points, respectively.

In each round, if you hit the pin 2, you will gain 6, 18, 54 points, respectively.

After the all rounds end, if the pin 1 is encircled by 1, 2, 3 hoops, then you will lose 9, 27, 81 points, respectively.

After the all rounds end, if the pin 2 is encircled by 1, 2, 3 hoops, then you will lose 6, 18, 54 points, respectively.

The optimal way in this example is to hit the pin 2 in the round 1 and hit the pin 1 in the round 2, and 3.

Sample Input 2

4 2
2 4 3 3
4 2 3 3
100000 100000 100000

Sample Output 2

210

Sample Input 3

20 19
3 2 3 4 3 3 2 3 2 2 3 3 4 3 2 4 4 3 3 4
2 3 4 2 4 3 3 2 4 2 4 3 3 2 3 4 4 4 2 2
3 4 5

Sample Output 3

-1417