Problem Statement

You are trying to implement collision detection in a 3D game.

In a 3-dimensional space, let C(a,b,c,d,e,f) denote the cuboid with a diagonal connecting (a,b,c) and (d,e,f), and with all faces parallel to the xy-plane, yz-plane, or zx-plane.
(This definition uniquely determines C(a,b,c,d,e,f).)

Given two cuboids C(a,b,c,d,e,f) and C(g,h,i,j,k,l), determine whether their intersection has a positive volume.

Constraints

• 0 \leq a < d \leq 1000
• 0 \leq b < e \leq 1000
• 0 \leq c < f \leq 1000
• 0 \leq g < j \leq 1000
• 0 \leq h < k \leq 1000
• 0 \leq i < l \leq 1000
• All input values are integers.

Sample Input 1

0 0 0 4 5 6
2 3 4 5 6 7

Sample Output 1

Yes

The positional relationship of the two cuboids is shown in the figure below, and their intersection has a volume of 8.

Sample Input 2

0 0 0 2 2 2
0 0 2 2 2 4

Sample Output 2

No

The two cuboids touch at a face, where the volume of the intersection is 0.

Sample Input 3

0 0 0 1000 1000 1000
10 10 10 100 100 100

Sample Output 3

Yes

Problem Statement

You are given integers A and B, in base K.
Print A \times B in decimal.

Notes

For base-K representation, see Wikipedia's article on Positional notation.

Constraints

• 2 \leq K \leq 10
• 1 \leq A,B \leq 10^5
• A and B are in base-K representation.

Sample Input 1

2
1011 10100

Sample Output 1

220

1011 in base 2 corresponds to 11 in base 10.
10100 in base 2 corresponds to 20 in base 10.
We have 11 \times 20 = 220, so print 220.

Sample Input 2

7
123 456

Sample Output 2

15642

123 in base 7 corresponds to 66 in base 10.
456 in base 7 corresponds to 237 in base 10.
We have 66 \times 237 = 15642, so print 15642.

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