Problem Statement

How many multiples of d are there among the integers between L and R (inclusive)?

Constraints

• All values in input are integers.
• 1 \leq L \leq R \leq 100
• 1 \leq d \leq 100

Sample Input 1

5 10 2

Sample Output 1

3

• Among the integers between 5 and 10, there are three multiples of 2: 6, 8, and 10.

Sample Input 2

6 20 7

Sample Output 2

2

• Among the integers between 6 and 20, there are two multiples of 7: 7 and 14.

Sample Input 3

1 100 1

Sample Output 3

100

Problem Statement

We have N squares assigned the numbers 1,2,3,\ldots,N. Each square has an integer written on it, and the integer written on Square i is a_i.

How many squares i satisfy both of the following conditions?

• The assigned number, i, is odd.
• The written integer is odd.

Constraints

• All values in input are integers.
• 1 \leq N, a_i \leq 100

Sample Input 1

5
1 3 4 5 7

Sample Output 1

2

• Two squares, Square 1 and 5, satisfy both of the conditions.
• For Square 2 and 4, the assigned numbers are not odd.
• For Square 3, the written integer is not odd.

Sample Input 2

15
13 76 46 15 50 98 93 77 31 43 84 90 6 24 14

Sample Output 2

3

Problem Statement

Let f(n) be the number of triples of integers (x,y,z) that satisfy both of the following conditions:

• 1 \leq x,y,z
• x^2 + y^2 + z^2 + xy + yz + zx = n

Given an integer N, find each of f(1),f(2),f(3),\ldots,f(N).

Constraints

• All values in input are integers.
• 1 \leq N \leq 10^4

Sample Input 1

20

Sample Output 1

0
0
0
0
0
1
0
0
0
0
3
0
0
0
0
0
3
3
0
0

• For n=6, only (1,1,1) satisfies both of the conditions. Thus, f(6) = 1.
• For n=11, three triples, (1,1,2), (1,2,1), and (2,1,1), satisfy both of the conditions. Thus, f(6) = 3.
• For n=17, three triples, (1,2,2), (2,1,2), and (2,2,1), satisfy both of the conditions. Thus, f(17) = 3.
• For n=18, three triples, (1,1,3), (1,3,1), and (3,1,1), satisfy both of the conditions. Thus, f(18) = 3.

Problem Statement

Let \mathrm{popcount}(n) be the number of 1s in the binary representation of n. For example, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3, and \mathrm{popcount}(0) = 0.

Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0: "replace n with the remainder when n is divided by \mathrm{popcount}(n)." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)

For example, when n=7, it becomes 0 after two operations, as follows:

• \mathrm{popcount}(7)=3, so we divide 7 by 3 and replace it with the remainder, 1.
• \mathrm{popcount}(1)=1, so we divide 1 by 1 and replace it with the remainder, 0.

You are given an integer X with N digits in binary. For each integer i such that 1 \leq i \leq N, let X_i be what X becomes when the i-th bit from the top is inverted. Find f(X_1), f(X_2), \ldots, f(X_N).

Constraints

• 1 \leq N \leq 2 \times 10^5
• X is an integer with N digits in binary, possibly with leading zeros.

Sample Input 1

3
011

Sample Output 1

2
1
1

• X_1 = 7, which will change as follows: 7 \rightarrow 1 \rightarrow 0. Thus, f(7) = 2.
• X_2 = 1, which will change as follows: 1 \rightarrow 0. Thus, f(1) = 1.
• X_3 = 2, which will change as follows: 2 \rightarrow 0. Thus, f(2) = 1.

Sample Input 2

23
00110111001011011001110

Sample Output 2

2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3

Problem Statement

We have N camels numbered 1,2,\ldots,N. Snuke has decided to make them line up in a row.

The happiness of Camel i will be L_i if it is among the K_i frontmost camels, and R_i otherwise.

Snuke wants to maximize the total happiness of the camels. Find the maximum possible total happiness of the camel.

Solve this problem for each of the T test cases given.

Constraints

• All values in input are integers.
• 1 \leq T \leq 10^5
• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq K_i \leq N
• 1 \leq L_i, R_i \leq 10^9
• The sum of values of N in each input file is at most 2 \times 10^5.

Sample Input 1

3
2
1 5 10
2 15 5
3
2 93 78
1 71 59
3 57 96
19
19 23 16
5 90 13
12 85 70
19 67 78
12 16 60
18 48 28
5 4 24
12 97 97
4 57 87
19 91 74
18 100 76
7 86 46
9 100 57
3 76 73
6 84 93
1 6 84
11 75 94
19 15 3
12 11 34

Sample Output 1

25
221
1354

• In the first test case, it is optimal to line up the camels in the order 2, 1.
  • Camel 1 is not the frontmost camel, so its happiness will be 10.
  • Camel 2 is among the two frontmost camels, so its happiness will be 15.
• In the second test case, it is optimal to line up the camels in the order 2, 1, 3.
  • Camel 1 is among the two frontmost camels, so its happiness will be 93.
  • Camel 2 is the frontmost camel, so its happiness will be 71.
  • Camel 3 is among the three frontmost camels, so its happiness will be 57.

Problem Statement

Given is an integer N. Snuke will choose integers s_1, s_2, n_1, n_2, u_1, u_2, k_1, k_2, e_1, and e_2 so that all of the following six conditions will be satisfied:

• 0 \leq s_1 < s_2
• 0 \leq n_1 < n_2
• 0 \leq u_1 < u_2
• 0 \leq k_1 < k_2
• 0 \leq e_1 < e_2
• s_1 + s_2 + n_1 + n_2 + u_1 + u_2 + k_1 + k_2 + e_1 + e_2 \leq N

For every possible choice (s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2), compute (s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1), and find the sum of all computed values, modulo (10^{9} +7).

Solve this problem for each of the T test cases given.

Constraints

• All values in input are integers.
• 1 \leq T \leq 100
• 1 \leq N \leq 10^{9}

Sample Input 1

4
4
6
10
1000000000

Sample Output 1

0
11
4598
257255556

• When N=4, there is no possible choice (s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2). Thus, the answer is 0.
• When N=6, there are six possible choices (s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2) as follows:
  • (0,1,0,1,0,1,0,1,0,1)
  • (0,2,0,1,0,1,0,1,0,1)
  • (0,1,0,2,0,1,0,1,0,1)
  • (0,1,0,1,0,2,0,1,0,1)
  • (0,1,0,1,0,1,0,2,0,1)
  • (0,1,0,1,0,1,0,1,0,2)
• We have one choice where (s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1) is 1 and five choices where (s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1) is 2, so the answer is 11.
• Be sure to find the sum modulo (10^{9} +7).