Problem Statement

There are N people, each of whom is either a child or an adult. The i-th person has a weight of W_i.
Whether each person is a child or an adult is specified by a string S of length N consisting of 0 and 1.
If the i-th character of S is 0, then the i-th person is a child; if it is 1, then the i-th person is an adult.

When Takahashi the robot is given a real number X, Takahashi judges a person with a weight less than X to be a child and a person with a weight more than or equal to X to be an adult.
For a real value X, let f(X) be the number of people whom Takahashi correctly judges whether they are children or adults.

Find the maximum value of f(X) for all real values of X.

Constraints

• 1\leq N\leq 2\times 10^5
• S is a string of length N consisting of 0 and 1.
• 1\leq W_i\leq 10^9
• N and W_i are integers.

Sample Input 1

5
10101
60 45 30 40 80

Sample Output 1

4

When Takahashi is given X=50, it judges the 2-nd, 3-rd, and 4-th people to be children and the 1-st and 5-th to be adults.
In reality, the 2-nd and 4-th are children, and the 1-st, 3-rd, and 5-th are adults, so the 1-st, 2-nd, 4-th, and 5-th people are correctly judged. Thus, f(50)=4.

This is the maximum since there is no X that judges correctly for all 5 people. Thus, 4 should be printed.

Sample Input 2

3
000
1 2 3

Sample Output 2

3

For example, X=10 achieves the maximum value f(10)=3.
Note that the people may be all children or all adults.

Sample Input 3

5
10101
60 50 50 50 60

Sample Output 3

4

For example, X=55 achieves the maximum value f(55)=4.
Note that there may be multiple people with the same weight.

Problem Statement

There is a 9\times 9 grid A, where each cell contains an integer between 1 and 9, inclusive.
Specifically, the cell at the i-th row from the top and j-th column from the left contains A_{i,j}.

If A satisfies all of the following conditions, print Yes. Otherwise, print No.

• For each row of A, the nine cells in that row contain each integer from 1 to 9 exactly once.
• For each column of A, the nine cells in that column contain each integer from 1 to 9 exactly once.
• Divide the rows of A into three groups, each of three rows, from top to bottom, and similarly divide the columns into three groups, each of three columns, from left to right. Each 3\times 3 grid obtained from A in this way contains each integer from 1 to 9 exactly once.

Constraints

• 1\leq A_{i,j}\leq 9
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

The grid A is shown below.

The grid A satisfies all three conditions, so print Yes.

Sample Input 2

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

Sample Output 2

No

The grid A is shown below.

For example, if you look at the top left 3\times 3 grid, you can see that the third condition is unsatisfied, so print No.

Sample Input 3

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

Sample Output 3

No

The grid A is shown below.

For example, if you look at the leftmost column, you can see that the second condition is unsatisfied, so print No.

Problem Statement

Given are a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) and a positive integer K.

For each i=K,K+1,\ldots,N, find the following.

• The K-th greatest value among the first i terms of P.

Constraints

• 1 \leq K \leq N \leq 5 \times 10^5
• (P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
• All values in input are integers.

Sample Input 1

3 2
1 2 3

Sample Output 1

1
2

• The (K=) 2-nd greatest value among the first 2 terms of P, (P_1,P_2)=(1,2), is 1.
• The (K=) 2-nd greatest value among the first 3 terms of P, (P_1,P_2,P_3)=(1,2,3), is 2.

Sample Input 2

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

Sample Output 2

2
3
3
5
6
7
7

Problem Statement

Takahashi is initially at his house and is about to visit Aoki's house.

There are N bus stops numbered 1 to N between the two houses, and Takahashi can move between them in the following ways:

• He can walk from his house to bus stop 1 in X units of time.
• For each i = 1, 2, \ldots, N-1, a bus departs from bus stop i at each time that is a multiple of P_i, and by taking this bus, he can get to bus stop (i+1) in T_i units of time. Here, the constraints guarantee that 1 \leq P_i \leq 8.
• Takahashi can walk from bus stop N to Aoki's house in Y units of time.

For each i = 1, 2, \ldots, Q, process the following query.

Find the earliest time that Takahashi can arrive at Aoki's house when he leaves his house at time q_i.

Note that if he arrives at a bus stop exactly at the departure time of a bus, he can take that bus.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq X, Y \leq 10^9
• 1 \leq P_i \leq 8
• 1 \leq T_i \leq 10^9
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq q_i \leq 10^9
• All input values are integers.

Sample Input 1

4 2 3
5 4
6 6
3 1
7
13
0
710511029
136397527
763027379
644706927
447672230

Sample Output 1

34
22
710511052
136397548
763027402
644706946
447672250

For the first query, Takahashi can move as follows to arrive at Aoki's house at time 34.

• Leave his house at time 13.
• Walk from his house and arrive at bus stop 1 at time 15.
• Take the bus departing from bus stop 1 at time 15 and arrive at bus stop 2 at time 19.
• Take the bus departing from bus stop 2 at time 24 and arrive at bus stop 3 at time 30.
• Take the bus departing from bus stop 3 at time 30 and arrive at bus stop 4 at time 31.
• Walk from bus stop 4 and arrive at Aoki's house at time 34.

For the second query, Takahashi can move as follows and arrive at Aoki's house at time 22.

• Leave his house at time 0.
• Walk from his house and arrive at bus stop 1 at time 2.
• Take the bus departing from bus stop 1 at time 5 and arrive at bus stop 2 at time 9.
• Take the bus departing from bus stop 2 at time 12 and arrive at bus stop 3 at time 18.
• Take the bus departing from bus stop 3 at time 18 and arrive at bus stop 4 at time 19.
• Walk from bus stop 4 and arrive at Aoki's house at time 22.

Problem Statement

There are N boxes numbered 1,2,\ldots,N, and 10^{100} balls numbered 1,2,\dots,10^{100}. Initially, box i contains just ball i.

Process a total of Q operations that will be performed.

There are three types of operations: 1, 2, and 3.

Type 1: Put all contents of box Y into box X. It is guaranteed that X \neq Y.

1 X Y

Type 2: Put ball k+1 into box X, where k is the current total number of balls contained in the boxes.

2 X

Type 3: Report the number of the box that contains ball X.

3 X

Constraints

• All values in the input are integers.
• 2 \le N \le 3 \times 10^5
• 1 \le Q \le 3 \times 10^5
• For each type-1 operation, 1 \le X,Y \le N and X \neq Y.
• For each type-2 operation, 1 \le X \le N.
• For each type-3 operation, ball X is contained in some box at that point.
• There is at least one type-3 operation.

Sample Input 1

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

Sample Output 1

5
4
3
1
3

This input contains ten operations.

• The first operation is of type 3. Ball 5 is in box 5.
• The second operation is of type 1. Put all contents of box 4 into box 1.
  • Box 1 now contains balls 1 and 4, and box 4 is now empty.
• The third operation is of type 2. Put ball 6 into box 1.
• The fourth operation is of type 2. Put ball 7 into box 4.
• The fifth operation is of type 3. Ball 7 is in box 4.
• The sixth operation is of type 1. Put all contents of box 1 into box 3.
  • Box 3 now contains balls 1, 3, 4, and 6, and box 1 is now empty.
• The seventh operation is of type 3. Ball 4 is in box 3.
• The eighth operation is of type 1. Put all contents of box 4 into box 1.
  • Box 1 now contains ball 7, and box 4 is now empty.
• The ninth operation is of type 3. Ball 7 is in box 1.
• The tenth operation is of type 3. Ball 6 is in box 3.