Problem Statement

You are given two sequences, each of length N, consisting of integers: A=(A_1, \ldots, A_N) and B=(B_1, \ldots, B_N).

Determine whether there is a sequence of length N, X=(X_1, \ldots, X_N), satisfying all of the conditions below.

• X_i = A_i or X_i = B_i, for every i(1\leq i\leq N).

• |X_i - X_{i+1}| \leq K, for every i(1\leq i\leq N-1).

Constraints

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

Sample Input 1

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

Sample Output 1

Yes

X=(9,6,3,7,5) satisfies all conditions.

Sample Input 2

4 90
1 1 1 100
1 2 3 100

Sample Output 2

No

No X satisfies all conditions.

Sample Input 3

4 1000000000
1 1 1000000000 1000000000
1 1000000000 1 1000000000

Sample Output 3

Yes

Problem Statement

You are given a string S of length N consisting of lowercase English letters. Each character of S is painted in one of the M colors: color 1, color 2, ..., color M; for each i = 1, 2, \ldots, N, the i-th character of S is painted in color C_i.

For each i = 1, 2, \ldots, M in this order, let us perform the following operation.

• Perform a right circular shift by 1 on the part of S painted in color i. That is, if the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters are painted in color i from left to right, then simultaneously replace the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters of S with the p_k-th, p_1-th, p_2-th, \ldots, p_{k-1}-th characters of S, respectively.

Print the final S after the above operations.

The constraints guarantee that at least one character of S is painted in each of the M colors.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq C_i \leq M
• N, M, and C_i are all integers.
• S is a string of length N consisting of lowercase English letters.
• For each integer 1 \leq i \leq M, there is an integer 1 \leq j \leq N such that C_j = i.

Sample Input 1

8 3
apzbqrcs
1 2 3 1 2 2 1 2

Sample Output 1

cszapqbr

Initially, S = apzbqrcs.

• For i = 1, perform a right circular shift by 1 on the part of S formed by the 1-st, 4-th, 7-th characters, resulting in S = cpzaqrbs.
• For i = 2, perform a right circular shift by 1 on the part of S formed by the 2-nd, 5-th, 6-th, 8-th characters, resulting in S = cszapqbr.
• For i = 3, perform a right circular shift by 1 on the part of S formed by the 3-rd character, resulting in S = cszapqbr (here, S is not changed).

Thus, you should print cszapqbr, the final S.

Sample Input 2

2 1
aa
1 1

Sample Output 2

aa

Problem Statement

The Republic of AtCoder lies on a Cartesian coordinate plane.
It has N towns, numbered 1,2,\dots,N. Town i is at (x_i, y_i), and no two different towns are at the same coordinates.

There are teleportation spells in the nation. A spell is identified by a pair of integers (a,b), and casting a spell (a, b) at coordinates (x, y) teleports you to (x+a, y+b).

Snuke is a great magician who can learn the spell (a, b) for any pair of integers (a, b) of his choice. The number of spells he can learn is also unlimited.
To be able to travel between the towns using spells, he has decided to learn some number of spells so that it is possible to do the following for every pair of different towns (i, j).

• Choose just one spell among the spells learned. Then, repeatedly use just the chosen spell to get from Town i to Town j.

At least how many spells does Snuke need to learn to achieve the objective above?

Constraints

• 2 \leq N \leq 500
• 0 \leq x_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq y_i \leq 10^9 (1 \leq i \leq N)
• (x_i, y_i) \neq (x_j, y_j) if i \neq j.

Sample Input 1

3
1 2
3 6
7 4

Sample Output 1

6

The figure below illustrates the positions of the towns (along with the coordinates of the four corners).

If Snuke learns the six spells below, he can get from Town i to Town j by using one of the spells once for every pair (i,j) (i \neq j), achieving his objective.

• (2, 4)
• (-2, -4)
• (4, -2)
• (-4, 2)
• (-6, -2)
• (6, 2)

Another option is to learn the six spells below. In this case, he can get from Town i to Town j by using one of the spells twice for every pair (i,j) (i \neq j), achieving his objective.

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

There is no combination of spells that consists of less than six spells and achieve the objective, so we should print 6.

Sample Input 2

3
1 2
2 2
4 2

Sample Output 2

2

The optimal choice is to learn the two spells below:

• (1, 0)
• (-1, 0)

Sample Input 3

4
0 0
0 1000000000
1000000000 0
1000000000 1000000000

Sample Output 3

8

Problem Statement

AtCoder Inc. is planning to develop a product. The product has K parameters, whose values are currently all zero. The company aims to raise all parameter values to at least P.

There are N development plans. Executing the i-th development plan (1 \le i \le N) increases the value of the j-th parameter by A_{i,j} for every integer j such that 1 \le j \le K, at the cost of C_i.

A development plan cannot be executed more than once. Determine whether the company can achieve its goal, and if it can, find the minimum total cost required to achieve the goal.

Constraints

• 1 \le N \le 100
• 1 \le K,P \le 5
• 0 \le A_{i,j} \le P(1 \le i \le N,1 \le j \le K)
• 1 \le C_i \le 10^9(1 \le i \le N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

9

If you execute the first, third, and fourth development plans, each parameter will be 3+2+0=5,0+4+1=5,2+0+4=6, all of which are at least 5, so the goal is achieved. The total cost in this case is 5 + 3 + 1 = 9.

It is impossible to achieve the goal at a total cost of 8 or less. Thus, the answer is 9.

Sample Input 2

7 3 5
85 1 0 1
37 1 1 0
38 2 0 0
45 0 2 2
67 1 1 0
12 2 2 0
94 2 2 1

Sample Output 2

-1

You cannot achieve the goal no matter what you do. Thus, print -1.

Problem Statement

There are N boxes numbered 1, 2, \ldots, N. Initially, box i contains one ball of color C_i.

You are given Q queries, which you should process in order.

Each query is given by a pair of integers (a,b) and asks you to do the following:

• Move all the balls from box a to box b, and then print the number of different colors of balls in box b.

Here, the boxes a and b may be empty.

Constraints

• 1 \leq N, Q \leq 200000
• 1 \leq C_i \leq N
• 1 \leq a, b \leq N
• a \neq b
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
2
1
1
3

• For the first query, move all the balls from box 1 to box 2. Box 2 now contains two balls of color 1, so print 1.

• For the second query, move all the balls from box 6 to box 4. Box 4 now contains one ball of color 2 and one ball of color 3, so print 2.

• For the third query, move all the balls from box 5 to box 1. Box 1 now contains one ball of color 2, so print 1.

• For the fourth query, move all the balls from box 3 to box 6. Box 6 now contains one ball of color 1, so print 1.

• For the fifth query, move all the balls from box 4 to box 6. Box 6 now contains one ball of color 1, one ball of color 2, and one ball of color 3, so print 3.

Sample Input 2

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

Sample Output 2

1
2
0