Problem Statement

You observed amoebae and kept some records.

Initially, there was one amoeba, numbered 1.

You made N records. According to the i-th record, the amoeba numbered A_i disappeared by dividing itself into two new amoebae, which were then numbered 2i and 2i+1.
Here, amoeba A_i is said to be the parent of amoebae 2i and 2i+1.

For each k=1,\ldots,2N+1, how many generations away is amoeba k from amoeba 1?

Constraints

• 1 \leq N \leq 2\times 10^5
• The records are consistent. That is:
  • 1\leq A_i \leq 2i-1.
  • A_i are distinct integers.

Sample Input 1

2
1 2

Sample Output 1

0
1
1
2
2

From amoeba 1, amoebae 2 and 3 were born. From amoeba 2, amoebae 4 and 5 were born.

• Amoeba 1 is zero generations away from amoeba 1.
• Amoeba 2 is one generation away from amoeba 1.
• Amoeba 3 is one generation away from amoeba 1.
• Amoeba 4 is one generation away from amoeba 2, and two generations away from amoeba 1.
• Amoeba 5 is one generation away from amoeba 2, and two generations away from amoeba 1.

Sample Input 2

4
1 3 5 2

Sample Output 2

0
1
1
2
2
3
3
2
2

Problem Statement

We have a sequence of N numbers: A = (a_1, a_2, \dots, a_N).
Process the Q queries explained below.

• Query i: You are given a pair of integers (x_i, k_i). Let us look at the elements of A one by one from the beginning: a_1, a_2, \dots Which element will be the k_i-th occurrence of the number x_i?
  Print the index of that element, or -1 if there is no such element.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq a_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
• 1 \leq k_i \leq N (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

6 8
1 1 2 3 1 2
1 1
1 2
1 3
1 4
2 1
2 2
2 3
4 1

Sample Output 1

1
2
5
-1
3
6
-1
-1

1 occurs in A at a_1, a_2, a_5. Thus, the answers to Query 1 through 4 are 1, 2, 5, -1 in this order.

Sample Input 2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

Sample Output 2

2
-1

Problem Statement

Takahashi and Aoki are playing a game.

• First, Takahashi chooses an integer between A and B (inclusive) and tells it to Aoki.
• Next, Aoki chooses an integer between C and D (inclusive).
• If the sum of these two integers is a prime, then Aoki wins; otherwise, Takahashi wins.

When the two players play optimally, which player will win?

Constraints

• 1 \leq A \leq B \leq 100
• 1 \leq C \leq D \leq 100
• All values in input are integers.

Sample Input 1

2 3 3 4

Sample Output 1

Aoki

For example, if Takahashi chooses 2, Aoki can choose 3 to make the sum 5, which is a prime.

Sample Input 2

1 100 50 60

Sample Output 2

Takahashi

If they play optimally, Takahashi always wins.

Sample Input 3

3 14 1 5

Sample Output 3

Aoki

Problem Statement

You are given a sequence of positive integers of length N: A=(A_1,A_2,\ldots,A_N). Find the number of triples of positive integers (i,j,k) that satisfy all of the following conditions:

• 1\leq i < j < k\leq N,
• A_i = A_k,
• A_i \neq A_j.

Constraints

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

Sample Input 1

5
1 2 1 3 2

Sample Output 1

3

The following three triples of positive integers (i,j,k) satisfy the conditions:

• (i,j,k)=(1,2,3)
• (i,j,k)=(2,3,5)
• (i,j,k)=(2,4,5)

Sample Input 2

7
1 2 3 4 5 6 7

Sample Output 2

0

There may be no triples of positive integers (i,j,k) that satisfy the conditions.

Sample Input 3

13
9 7 11 7 3 8 1 13 11 11 11 6 13

Sample Output 3

20

Problem Statement

Given are two sequences of N integers each: A = (A_1, A_2, \ldots, A_N) and B = (B_1, B_2 \ldots, B_N).

On the sequence A, you can do the two operations below any number of times (possibly zero) in any order.

• Choose an integer i satisfying 1 \leq i \leq N, and increase or decrease A_i by 1, for the cost of X yen (Japanese currency).
• Choose an integer i satisfying 1 \leq i \leq N-1, and swap the values of A_i and A_{i+1}, for the cost of Y yen.

Print the minimum total cost needed to make the sequence A equal the sequence B by repeating the above.

Constraints

• 2 \leq N \leq 18
• 1 \leq X \leq 10^8
• 1 \leq Y \leq 10^{16}
• 1 \leq A_i, B_i \leq 10^8
• All values in input are integers.

Sample Input 1

4 3 5
4 2 5 2
6 4 2 1

Sample Output 1

16

Initialy, we have A = (4, 2, 5, 2).
The following sequence of operations makes A equal B.

• Pay X = 3 yen to increase the value of A_3 by 1, making A = (4, 2, 6, 2).
• Pay Y = 5 yen to swap the values of A_2 and A_3, making A = (4, 6, 2, 2).
• Pay Y = 5 yen to swap the values of A_1 and A_2, making A = (6, 4, 2, 2).
• Pay X = 3 yen to decrease the value of A_4 by 1, making A = (6, 4, 2, 1).

The total cost of these operations is 3+5+5+3 = 16 yen, which is the minimum possible.

Sample Input 2

5 12345 6789
1 2 3 4 5
1 2 3 4 5

Sample Output 2

0

A and B are equal from the beginning, so no operation is needed.

Sample Input 3

18 20719114 5117250357733867
10511029 36397527 63027379 44706927 47672230 79861204 57882493 42931589 51053644 52300688 43971370 26515475 62139996 41282303 34022578 12523039 6696497 64922712
14720753 4621362 25269832 91410838 86751784 32741849 6602693 60719353 28911226 88280613 18745325 80675202 34289776 37849132 99280042 73760634 43897718 40659077

Sample Output 3

13104119429316474

Note that values in input or output may not fit into 32-bit integer types.