Problem Statement

A non-negative integer n is called a good integer when it satisfies the following condition:

• All digits in the decimal notation of n are even numbers (0, 2, 4, 6, and 8).

For example, 0, 68, and 2024 are good integers.

You are given an integer N. Find the N-th smallest good integer.

Constraints

• 1 \leq N \leq 10^{12}
• N is an integer.

Sample Input 1

8

Sample Output 1

24

The good integers in ascending order are 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, \dots.
The eighth smallest is 24, which should be printed.

Sample Input 2

133

Sample Output 2

2024

Sample Input 3

31415926535

Sample Output 3

2006628868244228

Problem Statement

You are given a positive integer N.
Find the number of quadruples of positive integers (A,B,C,D) such that AB + CD = N.

Under the constraints of this problem, it can be proved that the answer is at most 9 \times 10^{18}.

Constraints

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

Sample Input 1

4

Sample Output 1

8

Here are the eight desired quadruples.

• (A,B,C,D)=(1,1,1,3)
• (A,B,C,D)=(1,1,3,1)
• (A,B,C,D)=(1,2,1,2)
• (A,B,C,D)=(1,2,2,1)
• (A,B,C,D)=(1,3,1,1)
• (A,B,C,D)=(2,1,1,2)
• (A,B,C,D)=(2,1,2,1)
• (A,B,C,D)=(3,1,1,1)

Sample Input 2

292

Sample Output 2

10886

Sample Input 3

19876

Sample Output 3

2219958

Problem Statement

There are N villages on a number line. The i-th village is located at coordinate X_i, and has P_i villagers.

Answer Q queries. The i-th query is in the following format:

• Given integers L_i and R_i, find the total number of villagers living in villages located between coordinates L_i and R_i, inclusive.

Constraints

• 1\leq N,Q\leq 2\times 10^5
• -10^9\leq X_1 < X_2 < \ldots < X_N \leq 10^9
• 1\leq P_i\leq 10^9
• -10^9\leq L_i \leq R_i \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
5
10
0

Consider the first query. The villages between coordinates 1 and 1 are the village at coordinate 1, with 1 villager. Hence, the answer is 1.

Consider the second query. The villages between coordinates 2 and 6 are the villages at coordinates 3 and 5, with 2 and 3 villagers, respectively. Hence, the answer is 2+3=5.

Sample Input 2

7
-10 -5 -3 -1 0 1 4
2 5 6 5 2 1 7
8
-7 7
-1 5
-10 -4
-8 10
-5 0
-10 5
-8 7
-8 -3

Sample Output 2

26
15
7
26
18
28
26
11

Problem Statement

There are N rectangular cuboids in a three-dimensional space.

These cuboids do not overlap. Formally, for any two different cuboids among them, their intersection has a volume of 0.

The diagonal of the i-th cuboid is a segment that connects two points (X_{i,1},Y_{i,1},Z_{i,1}) and (X_{i,2},Y_{i,2},Z_{i,2}), and its edges are all parallel to one of the coordinate axes.

For each cuboid, find the number of other cuboids that share a face with it.
Formally, for each i, find the number of j with 1\leq j \leq N and j\neq i such that the intersection of the surfaces of the i-th and j-th cuboids has a positive area.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq X_{i,1} < X_{i,2} \leq 100
• 0 \leq Y_{i,1} < Y_{i,2} \leq 100
• 0 \leq Z_{i,1} < Z_{i,2} \leq 100
• Cuboids do not have an intersection with a positive volume.
• All input values are integers.

Sample Input 1

4
0 0 0 1 1 1
0 0 1 1 1 2
1 1 1 2 2 2
3 3 3 4 4 4

Sample Output 1

1
1
0
0

The 1-st and 2-nd cuboids share a rectangle whose diagonal is the segment connecting two points (0,0,1) and (1,1,1).
The 1-st and 3-rd cuboids share a point (1,1,1), but do not share a surface.

Sample Input 2

3
0 0 10 10 10 20
3 4 1 15 6 10
0 9 6 1 20 10

Sample Output 2

2
1
1

Sample Input 3

8
0 0 0 1 1 1
0 0 1 1 1 2
0 1 0 1 2 1
0 1 1 1 2 2
1 0 0 2 1 1
1 0 1 2 1 2
1 1 0 2 2 1
1 1 1 2 2 2

Sample Output 3

3
3
3
3
3
3
3
3

Problem Statement

There are N towns numbered 1,\ldots,N and M roads numbered 1,\ldots,M.

Road i connects towns A_i and B_i. When you use a road, your score changes as follows:

• when you move from town A_i to town B_i using road i, your score increases by C_i; when you move from town B_i to town A_i using road i, your score decreases by C_i.

Your score may become negative.

Answer the following Q questions.

• If you start traveling from town X_i with initial score 0, find the maximum possible score when you are at town Y_i.
  Here, if you cannot get from town X_i to town Y_i, print nan instead; if you can have as large a score as you want when you are at town Y_i, print inf instead.

Constraints

• 2\leq N \leq 10^5
• 0\leq M \leq 10^5
• 1\leq Q \leq 10^5
• 1\leq A_i,B_i,X_i,Y_i \leq N
• 0\leq C_i \leq 10^9
• All values in the input are integers.

Sample Input 1

5 5 3
1 2 1
1 2 2
3 4 1
4 5 1
3 5 2
5 3
1 2
3 1

Sample Output 1

-2
inf
nan

For the first question, if you use road 5 to move from town 5 to town 3, you can have a score -2 when you are at town 3.
Since you cannot make the score larger, the answer is -2.

For the second question, you can have as large a score as you want when you are at town 2 if you travel as follows: repeatedly "use road 2 to move from town 1 to town 2 and then use road 1 to move from town 2 to town 1" as many times as you want, and finally use road 2 to move from town 1 to town 2.

For the third question, you cannot get from town 3 to town 1.

Sample Input 2

2 1 1
1 1 1
1 1

Sample Output 2

inf

The endpoints of a road may be the same, and so may the endpoints given in a question.

Sample Input 3

9 7 5
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

Sample Output 3

inf
nan
nan
inf
-9