Problem Statement

You have an empty sequence and N balls. The size of the i-th ball (1 \leq i \leq N) is 2^{A_i}.

You will perform N operations.
In the i-th operation, you add the i-th ball to the right end of the sequence, and repeat the following steps:

1. If the sequence has one or fewer balls, end the operation.
2. If the rightmost ball and the second rightmost ball in the sequence have different sizes, end the operation.
3. If the rightmost ball and the second rightmost ball in the sequence have the same size, remove these two balls and add a new ball to the right end of the sequence with a size equal to the sum of the sizes of the two removed balls. Then, go back to step 1 and repeat the process.

Determine the number of balls remaining in the sequence after the N operations.

Constraints

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

Sample Input 1

7
2 1 1 3 5 3 3

Sample Output 1

3

The operations proceed as follows:

• After the first operation, the sequence has one ball, of size 2^2.
• After the second operation, the sequence has two balls, of sizes 2^2 and 2^1 in order.
• After the third operation, the sequence has one ball, of size 2^3. This is obtained as follows:
  • When the third ball is added during the third operation, the sequence has balls of sizes 2^2, 2^1, 2^1 in order.
  • The first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^1 + 2^1 = 2^2 is added. Now, the sequence has balls of sizes 2^2, 2^2.
  • Again, the first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^2 + 2^2 = 2^3 is added, leaving the sequence with a ball of size 2^3.
• After the fourth operation, the sequence has one ball, of size 2^4.
• After the fifth operation, the sequence has two balls, of sizes 2^4 and 2^5 in order.
• After the sixth operation, the sequence has three balls, of sizes 2^4, 2^5, 2^3 in order.
• After the seventh operation, the sequence has three balls, of sizes 2^4, 2^5, 2^4 in order.

Therefore, you should print 3, the final number of balls in the sequence.

Sample Input 2

5
0 0 0 1 2

Sample Output 2

4

The operations proceed as follows:

• After the first operation, the sequence has one ball, of size 2^0.
• After the second operation, the sequence has one ball, of size 2^1.
• After the third operation, the sequence has two balls, of sizes 2^1 and 2^0 in order.
• After the fourth operation, the sequence has three balls, of sizes 2^1, 2^0, 2^1 in order.
• After the fifth operation, the sequence has four balls, of sizes 2^1, 2^0, 2^1, 2^2 in order.

Therefore, you should print 4, the final number of balls in the sequence.

Problem Statement

There is a 10^9-story building with N ladders.
Takahashi, who is on the 1-st (lowest) floor, wants to reach the highest floor possible by using ladders (possibly none).
The ladders are numbered from 1 to N, and ladder i connects the A_i-th and B_i-th floors. One can use ladder i in either direction to move from the A_i-th floor to the B_i-th floor or vice versa, but not between other floors.
Takahashi can freely move within the same floor, but cannot move between floors without using ladders.
What is the highest floor Takahashi can reach?

Constraints

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

Sample Input 1

4
1 4
4 3
4 10
8 3

Sample Output 1

10

He can reach the 10-th floor by using ladder 1 to get to the 4-th floor and then ladder 3 to get to the 10-th floor.

Sample Input 2

6
1 3
1 5
1 12
3 5
3 12
5 12

Sample Output 2

12

Sample Input 3

3
500000000 600000000
600000000 700000000
700000000 800000000

Sample Output 3

1

He may be unable to move between floors.

Problem Statement

You are given a string S consisting of uppercase and lowercase English letters.

We perform the following operation on S 10^{100} times:

• First, create a string T by changing uppercase letters in S to lowercase, and lowercase letters to uppercase.
• Then, concatenate S and T in this order to form a new S.

Answer Q queries. The i-th query is as follows:

• Find the K_i-th character from the beginning of S after all operations are completed.

Constraints

• S is a string consisting of uppercase and lowercase English letters, with length between 1 and 2 \times 10^5, inclusive.
• Q and K_i are integers.
• 1 \le Q \le 2 \times 10^5
• 1 \le K_i \le 10^{18}

Sample Input 1

aB
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Sample Output 1

a B A b A b a B A b a B a B A b

Before the operations, S = aB.

• After performing the operation once on aB, it becomes aBAb.
• After performing the operation twice on aB, it becomes aBAbAbaB.
• \dots

After performing the operation 10^{100} times, S = aBAbAbaBAbaBaBAb...

Sample Input 2

qWeRtYuIoP
8
1 1 2 3 5 8 13 21

Sample Output 2

q q W e t I E Q

Sample Input 3

AnUoHrjhgfLMcDIpzxXmEWPwBZvbKqQuiJTtFSlkNGVReOYCdsay
5
1000000000000000000 123456789 1 987654321 999999999999999999

Sample Output 3

K a A Z L

Problem Statement

Takahashi has a secret integer sequence a. You know that the length of a is N.

You want to guess the contents of a. He has promised to give you the following Q additional pieces of information.

• The i-th information: the value a_{l_i}+a_{l_i+1}+\cdots+a_{r_i}.

Is it possible to determine the sum of all elements in a, a_1+a_2+\cdots+a_N, if the Q pieces of promised information are given?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq \min(2 \times 10^5,\frac{N(N+1)}{2})
• 1 \leq l_i \leq r_i \leq N
• (l_i,r_i) \neq (l_j,r_j)\ (i \neq j)
• All values in input are integers.

Sample Input 1

3 3
1 2
2 3
2 2

Sample Output 1

Yes

From the first and second information, we can find the value a_1+a_2+a_2+a_3. By subtracting the value of a_2 from it, we can determine the value a_1+a_2+a_3.

Sample Input 2

4 3
1 3
1 2
2 3

Sample Output 2

No

We can determine the sum of the first 3 elements of a, but not the sum of all elements.

Sample Input 3

4 4
1 1
2 2
3 3
1 4

Sample Output 3

Yes

The fourth information directly gives us the sum of all elements.

Problem Statement

There is an N\times N grid, and the cell at the i-th row from the top and the j-th column from the left (1\leq i,j\leq N) contains the integer A _ {i,j}.

You are given an integer M. When choosing three non-overlapping M\times M grids, find the maximum possible sum of the integers written in the chosen grids.

Constraints

• 2\leq N\leq 1000
• 1\leq M\leq N/2
• 0\leq A _ {i,j}\leq10 ^ 9
• All input values are integers.

Sample Input 1

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

Sample Output 1

154

From the given grid, if we choose three 3\times3 grids as shown in the figure below (this corresponds to setting (i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3)=(1,5,2,1,5,2)), the sum of the numbers written in the chosen grids will be 154.

There is no way to make the sum 155 or greater while satisfying the conditions in the problem statement, so print 154.

Sample Input 2

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

Sample Output 2

27

The following choice is optimal.

Sample Input 3

16 4
74 16 58 32 97 52 43 51 40 58 13 24 65 11 63 29
98 75 40 77 15 50 83 85 35 46 38 37 56 38 63 55
95 42 10 70 53 40 25 10 70 32 33 19 52 79 74 58
33 91 53 11 65 63 78 77 81 46 81 63 11 82 55 62
39 95 92 69 77 89 14 84 53 78 71 81 66 39 96 29
74 26 60 55 89 35 32 64 17 26 74 92 84 33 59 82
23 69 10 95 94 14 58 58 97 95 62 58 72 55 71 43
93 77 27 87 74 72 91 37 53 80 51 71 37 35 97 46
81 88 26 79 78 30 53 68 83 28 59 28 74 55 20 86
93 13 25 19 53 53 17 24 69 14 67 81 10 19 69 90
88 83 62 92 22 31 27 34 67 48 42 32 68 14 96 87
44 69 25 48 68 42 53 82 44 42 96 31 13 56 68 83
63 87 24 75 16 70 63 99 95 10 63 26 56 12 77 49
94 83 69 95 48 41 40 97 45 61 26 38 83 91 44 31
43 69 54 64 20 60 17 15 62 25 58 50 59 63 88 70
72 95 21 28 41 14 77 22 64 78 33 55 67 51 78 40

Sample Output 3

3295

The following choice is optimal.