Problem Statement

You are given a positive integer N.

Find the maximum value of a palindromic cube number not greater than N.

Here, a positive integer K is defined to be a palindromic cube number if and only if it satisfies the following two conditions:

• There is a positive integer x such that x^3 = K.
• The decimal representation of K without leading zeros is a palindrome. More precisely, if K is represented as K = \sum_{i = 0}^{L-1} A_i10^i using integers A_0, A_1, \ldots, A_{L-2} between 0 and 9, inclusive, and an integer A_{L-1} between 1 and 9, inclusive, then A_i = A_{L-1-i} for all i = 0, 1, \ldots, L-1.

Constraints

• N is a positive integer not greater than 10^{18}.

Sample Input 1

345

Sample Output 1

343

343 is a palindromic cube number, while 344 and 345 are not. Thus, the answer is 343.

Sample Input 2

6

Sample Output 2

1

Sample Input 3

123456789012345

Sample Output 3

1334996994331

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N). You can perform the following operation any number of times (possibly zero).

• Choose integers i and j with 1\leq i,j \leq N. Decrease A_i by one and increase A_j by one.

Find the minimum number of operations required to make the difference between the minimum and maximum values of A at most one.

Constraints

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

Sample Input 1

4
4 7 3 7

Sample Output 1

3

By the following three operations, the difference between the minimum and maximum values of A becomes at most one.

• Choose i=2 and j=3 to make A=(4,6,4,7).
• Choose i=4 and j=1 to make A=(5,6,4,6).
• Choose i=4 and j=3 to make A=(5,6,5,5).

You cannot make the difference between maximum and minimum values of A at most one by less than three operations, so the answer is 3.

Sample Input 2

1
313

Sample Output 2

0

Sample Input 3

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

Sample Output 3

2499999974

Problem Statement

There is a grid with 10^9 by 10^9 squares. Let (i, j) denote the square at the (i + 1)-th row from the top and the (j + 1)-th column from the left (0 \leq i, j \lt 10^9). (Note the unusual index assignment.)
Each square is black or white. The color of the square (i, j) is represented by a character P[i \bmod N][j \bmod N], where B means black, and W means white. Here, a \bmod b denotes the remainder when a is divided by b.

Answer Q queries.
Each query gives you four integers A, B, C, D and asks you to find the number of black squares contained in the rectangular area with (A, B) as the top-left corner and (C, D) as the bottom-right corner.

Constraints

• 1 \leq N \leq 1000
• P[i][j] is W or B.
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A \leq C \lt 10^9
• 0 \leq B \leq D \lt 10^9
• N, Q, A, B, C, D are all integers.

Sample Input 1

3 2
WWB
BBW
WBW
1 2 3 4
0 3 4 5

Sample Output 1

4
7

The figure below illustrates the upper left part of the grid.

For the first query, the rectangular area with (1, 2) as the top-left corner and (3, 4) as the bottom-right corner, surrounded by the red frame in the figure, contains four black squares.
For the second query, the rectangular area with (0, 3) as the top-left corner and (4, 5) as the bottom-right corner, surrounded by the blue frame in the figure, contains seven black squares.

Sample Input 2

10 5
BBBWWWBBBW
WWWWWBBBWB
BBBWBBWBBB
BBBWWBWWWW
WWWWBWBWBW
WBBWBWBBBB
WWBBBWWBWB
WBWBWWBBBB
WBWBWBBWWW
WWWBWWBWWB
5 21 21 93
35 35 70 43
55 72 61 84
36 33 46 95
0 0 999999999 999999999

Sample Output 2

621
167
44
344
500000000000000000

Problem Statement

We have a variable X and N kinds of operations that change the value of X. Operation i is represented as a pair of integers (T_i,A_i), and is the following operation:

• if T_i=1, it replaces the value of X with X\ {\rm and}\ A_i;
• if T_i=2, it replaces the value of X with X\ {\rm or}\ A_i;
• if T_i=3, it replaces the value of X with X\ {\rm xor}\ A_i.

Initialize X with the value of C and execute the following procedures in order:

• Perform Operation 1, and then print the resulting value of X.
• Next, perform Operation 1, 2 in this order, and then print the value of X.
• Next, perform Operation 1, 2, 3 in this order, and then print the value of X.
• \vdots
• Next, perform Operation 1, 2, \ldots, N in this order, and then print the value of X.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1\leq T_i \leq 3
• 0\leq A_i \lt 2^{30}
• 0\leq C \lt 2^{30}
• All values in input are integers.

Sample Input 1

3 10
3 3
2 5
1 12

Sample Output 1

9
15
12

The initial value of X is 10.

• Operation 1 changes X to 9.
• Next, Operation 1 changes X to 10, and then Operation 2 changes it to 15.
• Next, Operation 1 changes X to 12, and then Operation 2 changes it to 13, and then Operation 3 changes it to 12.

Sample Input 2

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

Sample Output 2

0
2
1
0
5
3
3
11
2

Problem Statement

Takahashi is at the origin of a number line. Takahashi wants to reach the goal at coordinate X.

Also, there are N walls and N hammers on the number line.

• At coordinates Y_1,Y_2,\dots,Y_N are walls of types 1,2,\dots,N, respectively.
  • Initially, Takahashi cannot get over the walls.
• At coordinates Z_1,Z_2,\dots,Z_N are hammers of types 1,2,\dots,N, respectively.
  • When he arrives at a coordinate with a hammer, he obtains the hammer.
  • The hammer of type i is dedicated to destroying the wall of type i. After he obtains the hammer of type i, he can destroy the wall of type i and get over it.

Determine if he can reach the goal. If he can, find the minimum distance he travels.

Constraints

• All values in the input are integers.
• 1 \le N \le 1500
• 1 \le |X|,|Y_i|,|Z_i| \le 10^9
• The (2 \times N + 1) coordinates X,Y_i and Z_i are distinct.

Sample Input 1

3 10
-2 8 -5
5 -10 3

Sample Output 1

40

Takahashi can reach the goal by traveling a distance of 40 as follows, which is the minimum possible:

• He starts at coordinate 0.
• He moves to coordinate 3 to obtain the hammer of type 3.
• He moves to coordinate 5 to obtain the hammer of type 1.
• He moves to coordinate -2 to destroy the wall of type 1.
• He moves to coordinate -5 to destroy the wall of type 3.
• He moves to coordinate -10 to obtain the hammer of type 2.
• He moves to coordinate 8 to destroy the wall of type 2.
• He moves to coordinate 10, which is the goal.

Sample Input 2

5 -1
10 -20 30 -40 50
-10 20 -30 40 -50

Sample Output 2

1

It may not be required that he obtains a hammer or destroys a wall to reach the goal.

Sample Input 3

1 100
30
60

Sample Output 3

-1

Takahashi cannot obtain the hammer of type 1, and neither can he reach the goal.

Sample Input 4

4 865942261
703164879 -531670946 -874856231 -700164975
-941120316 599462305 -649785130 665402307

Sample Output 4

4078987507