Problem Statement

You are given an integer N at least 100. Print the last two digits of N.

Strictly speaking, print the tens and ones digits of N in this order.

Constraints

• 100 \le N \le 999
• N is an integer.

Sample Input 1

254

Sample Output 1

54

The last two digits of 254 are 54, which should be printed.

Sample Input 2

101

Sample Output 2

01

The last two digits of 101 are 01, which should be printed.

Problem Statement

Find the N integer sequences A_0,\ldots,A_{N-1} defined as follows.

• For each i (0\leq i \leq N-1), the length of A_i is i+1.
• For each i and j (0\leq i \leq N-1, 0 \leq j \leq i), the (j+1)-th term of A_i, denoted by a_{i,j}, is defined as follows.
  • a_{i,j}=1, if j=0 or j=i.
  • a_{i,j} = a_{i-1,j-1} + a_{i-1,j}, otherwise.

Constraints

• 1 \leq N \leq 30
• N is an integer.

Sample Input 1

3

Sample Output 1

1
1 1
1 2 1

Sample Input 2

10

Sample Output 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Problem Statement

We have a sequence of length N: A=(a_1,\ldots,a_N). Additionally, you are given an integer K.

You can perform the following operation zero or more times.

• Choose an integer i such that 1 \leq i \leq N-K, then swap the values of a_i and a_{i+K}.

Determine whether it is possible to sort A in ascending order.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N-1
• 1 \leq a_i \leq 10^9
• All values in input are integers.

Sample Input 1

5 2
3 4 1 3 4

Sample Output 1

Yes

The following sequence of operations sorts A in ascending order.

• Choose i=1 to swap the values of a_1 and a_3. A is now (1,4,3,3,4).
• Choose i=2 to swap the values of a_2 and a_4. A is now (1,3,3,4,4).

Sample Input 2

5 3
3 4 1 3 4

Sample Output 2

No

Sample Input 3

7 5
1 2 3 4 5 5 10

Sample Output 3

Yes

No operations may be needed.

Problem Statement

You are given an integer N. Find the number of pairs (i,j) of positive integers at most N that satisfy the following condition:

• i \times j is a square number.

Constraints

• 1 \le N \le 2 \times 10^5
• N is an integer.

Sample Input 1

4

Sample Output 1

6

The six pairs (1,1),(1,4),(2,2),(3,3),(4,1),(4,4) satisfy the condition.

On the other hand, (2,3) does not, since 2 \times 3 =6 is not a square number.

Sample Input 2

254

Sample Output 2

896

Problem Statement

We have a simple undirected graph with N vertices and M edges. The vertices are numbered 1,\ldots,N. For each i=1,\ldots,M, the i-th edge connects Vertex a_i and Vertex b_i. Additionally, the degree of each vertex is at most 3.

For each i=1,\ldots,Q, answer the following query.

• Find the sum of indices of vertices whose distances from Vertex x_i are at most k_i.

Constraints

• 1 \leq N \leq 1.5 \times 10^5
• 0 \leq M \leq \min (\frac{N(N-1)}{2},\frac{3N}{2})
• 1 \leq a_i \lt b_i \leq N
• (a_i,b_i) \neq (a_j,b_j), if i\neq j.
• The degree of each vertex in the graph is at most 3.
• 1 \leq Q \leq 1.5 \times 10^5
• 1 \leq x_i \leq N
• 0 \leq k_i \leq 3
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
20
2
20
7
6
20

For the 1-st query, the only vertex whose distance from Vertex 1 is at most 1 is Vertex 1, so the answer is 1.
For the 2-nd query, the vertices whose distances from Vertex 2 are at most 2 are Vertex 2, 3, 4, 5, and 6, so the answer is their sum, 20.
The 3-rd and subsequent queries can be answered similarly.

Problem Statement

You are given a positive integer N and sequences of N positive integers each: A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).

We have an N \times N grid. The square at the i-th row from the top and the j-th column from the left is called the square (i,j). For each pair of integers (i,j) such that 1 \le i,j \le N, the square (i,j) has the integer A_i + B_j written on it. Process Q queries of the following form.

• You are given a quadruple of integers h_1,h_2,w_1,w_2 such that 1 \le h_1 \le h_2 \le N,1 \le w_1 \le w_2 \le N. Find the greatest common divisor of the integers contained in the rectangle region whose top-left and bottom-right corners are (h_1,w_1) and (h_2,w_2), respectively.

Constraints

• 1 \le N,Q \le 2 \times 10^5
• 1 \le A_i,B_i \le 10^9
• 1 \le h_1 \le h_2 \le N
• 1 \le w_1 \le w_2 \le N
• All values in input are integers.

Sample Input 1

3 5
3 5 2
8 1 3
1 2 2 3
1 3 1 3
1 1 1 1
2 2 2 2
3 3 1 1

Sample Output 1

2
1
11
6
10

Let C_{i,j} denote the integer on the square (i,j).

For the 1-st query, we have C_{1,2}=4,C_{1,3}=6,C_{2,2}=6,C_{2,3}=8, so the answer is their greatest common divisor, which is 2.

Sample Input 2

1 1
9
100
1 1 1 1

Sample Output 2

109

Problem Statement

There is a complex composed of N 10^9-story skyscrapers. The skyscrapers are numbered 1 to N, and the floors are numbered 1 to 10^9.

From any floor of any skyscraper, one can use a skybridge to get to the same floor of any other skyscraper in one minute.

Additionally, there are M elevators. The i-th elevator runs between Floor B_i and Floor C_i of Skyscraper A_i. With this elevator, one can get from Floor x to Floor y of Skyscraper A_i in |x-y| minutes, for every pair of integers x,y such that B_i \le x,y \le C_i.

Answer the following Q queries.

• Determine whether it is possible to get from Floor Y_i of Skyscraper X_i to Floor W_i of Skyscraper Z_i, and find the shortest time needed to get there if it is possible.

Constraints

• 1 \le N,M,Q \le 2 \times 10^5
• 1 \le A_i \le N
• 1 \le B_i < C_i \le 10^9
• 1 \le X_i,Z_i \le N
• 1 \le Y_i,W_i \le 10^9
• All values in input are integers.

Sample Input 1

3 4 3
1 2 10
2 3 7
3 9 14
3 1 3
1 3 3 14
3 1 2 7
1 100 1 101

Sample Output 1

12
7
-1

For the 1-st query, you can get to the destination in 12 minutes as follows.

• Use Elevator 1 to get from Floor 3 to Floor 9 of Skyscraper 1, in 6 minutes.
• Use the skybridge on Floor 9 to get from Skyscraper 1 to Skyscraper 3, in 1 minute.
• Use Elevator 3 to get from Floor 9 to Floor 14 of Skyscraper 3, in 5 minutes.

For the 3-rd query, the destination is unreachable, so -1 should be printed.

Sample Input 2

1 1 1
1 1 2
1 1 1 2

Sample Output 2

1

Problem Statement

You are given multisets with N non-negative integers each: A=\{ a_1,\ldots,a_N \} and B=\{ b_1,\ldots,b_N \}.
You can perform the operations below any number of times in any order.

• Choose a non-negative integer x in A. Delete one instance of x from A and add one instance of 2x instead.
• Choose a non-negative integer x in A. Delete one instance of x from A and add one instance of \left\lfloor \frac{x}{2} \right\rfloor instead. (\lfloor x \rfloor is the greatest integer not exceeding x.)

Your objective is to make A and B equal (as multisets).
Determine whether it is achievable, and find the minimum number of operations needed to achieve it if it is achievable.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq a_1 \leq \ldots \leq a_N \leq 10^9
• 0 \leq b_1 \leq \ldots \leq b_N \leq 10^9
• All values in input are integers.

Sample Input 1

3
3 4 5
2 4 6

Sample Output 1

2

You can achieve the objective in two operations as follows.

• Choose x=3 to delete one instance of x\, (=3) from A and add one instance of 2x\, (=6) instead. Now we have A=\{4,5,6\}.
• Choose x=5 to delete one instance of x\, (=5) from A and add one instance of \left\lfloor \frac{x}{2} \right\rfloor \, (=2) instead. Now we have A=\{2,4,6\}.

Sample Input 2

1
0
1

Sample Output 2

-1

You cannot turn \{ 0 \} into \{ 1 \} .