Problem Statement

There are N types of elements numbered 1, 2, \ldots, N.

Elements can be combined with each other. When elements i and j are combined, they transform into element A_{i, j} if i \geq j, and into element A_{j, i} if i < j.

Starting with element 1, combine it with elements 1, 2, \ldots, N in this order. Find the final element obtained.

Constraints

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

Sample Input 1

4
3
2 4
3 1 2
2 1 2 4

Sample Output 1

2

• Combining element 1 with element 1 results in element 3.

• Combining element 3 with element 2 results in element 1.

• Combining element 1 with element 3 results in element 3.

• Combining element 3 with element 4 results in element 2.

Therefore, the value to be printed is 2.

Sample Input 2

5
5
5 5
5 5 5
5 5 5 5
5 5 5 5 5

Sample Output 2

5

Sample Input 3

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

Sample Output 3

5

Problem Statement

You are given integer sequences, each of length N: A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_N).
All elements of A are different. All elements of B are different, too.

Print the following two values.

1. The number of integers contained in both A and B, appearing at the same position in the two sequences. In other words, the number of integers i such that A_i = B_i.
2. The number of integers contained in both A and B, appearing at different positions in the two sequences. In other words, the number of pairs of integers (i, j) such that A_i = B_j and i \neq j.

Constraints

• 1 \leq N \leq 1000
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• A_1, A_2, \dots, A_N are all different.
• B_1, B_2, \dots, B_N are all different.
• All values in input are integers.

Sample Input 1

4
1 3 5 2
2 3 1 4

Sample Output 1

1
2

There is one integer contained in both A and B, appearing at the same position in the two sequences: A_2 = B_2 = 3.
There are two integers contained in both A and B, appearing at different positions in the two sequences: A_1 = B_3 = 1 and A_4 = B_1 = 2.

Sample Input 2

3
1 2 3
4 5 6

Sample Output 2

0
0

In both 1. and 2., no integer satisfies the condition.

Sample Input 3

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

Sample Output 3

3
2

Problem Statement

There are N creatures standing in a circle, called Snuke 1, 2, ..., N in counter-clockwise order.

When Snuke i (1 \leq i \leq N) receives a gem at time t, S_i units of time later, it will hand that gem to Snuke i+1 at time t+S_i. Here, Snuke N+1 is Snuke 1.

Additionally, Takahashi will hand a gem to Snuke i at time T_i.

For each i (1 \leq i \leq N), find the time when Snuke i receives a gem for the first time. Assume that it takes a negligible time to hand a gem.

Constraints

• 1 \leq N \leq 200000
• 1 \leq S_i,T_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
4 1 5
3 10 100

Sample Output 1

3
7
8

We will list the three Snuke's and Takahashi's actions up to time 13 in chronological order.

Time 3: Takahashi hands a gem to Snuke 1.

Time 7: Snuke 1 hands a gem to Snuke 2.

Time 8: Snuke 2 hands a gem to Snuke 3.

Time 10: Takahashi hands a gem to Snuke 2.

Time 11: Snuke 2 hands a gem to Snuke 3.

Time 13: Snuke 3 hands a gem to Snuke 1.

After that, they will continue handing gems, though it will be irrelevant to the answer.

Sample Input 2

4
100 100 100 100
1 1 1 1

Sample Output 2

1
1
1
1

Note that the values S_i and T_i may not be distinct.

Sample Input 3

4
1 2 3 4
1 2 4 7

Sample Output 3

1
2
4
7

Note that a Snuke may perform multiple transactions simultaneously. Particularly, a Snuke may receive gems simultaneously from Takahashi and another Snuke.

Sample Input 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

Sample Output 4

50
22
63
28
44
60
64
27

Problem Statement

You have N socks. The color of the i-th sock is A_i.

You want to perform the following operation as many times as possible. How many times can it be performed at most?

• Choose two same-colored socks that are not paired yet, and pair them.

Constraints

• 1\leq N \leq 5\times 10^5
• 1\leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
4 1 7 4 1 4

Sample Output 1

2

You can do the operation twice as follows.

• Choose two socks with the color 1 and pair them.
• Choose two socks with the color 4 and pair them.

Then, you will be left with one sock with the color 4 and another with the color 7, so you can no longer do the operation. There is no way to do the operation three or more times, so you should print 2.

Sample Input 2

1
158260522

Sample Output 2

0

Sample Input 3

10
295 2 29 295 29 2 29 295 2 29

Sample Output 3

4

Problem Statement

There is a sequence that contains one 0, A=(0).
Additionally, you are given a string of length N, S=s_1s_2\ldots s_N, consisting of L and R.

For each i=1, 2, \ldots, N in this order, the following will be done.

• If s_i is L, insert i to the immediate left of i-1 in A.
• If s_i is R, insert i to the immediate right of i-1 in A.

Find the final contents of A.

Constraints

• 1\leq N \leq 5\times 10^5
• N is an integer.
• |S| = N
• s_i is L or R.

Sample Input 1

5
LRRLR

Sample Output 1

1 2 4 5 3 0

Initially, A=(0).
S_1 is L, which makes it A=(1,0).
S_2 is R, which makes it A=(1,2,0).
S_3 is R, which makes it A=(1,2,3,0).
S_4 is L, which makes it A=(1,2,4,3,0).
S_5 is R, which makes it A=(1,2,4,5,3,0).

Sample Input 2

7
LLLLLLL

Sample Output 2

7 6 5 4 3 2 1 0