Problem Statement

Takahashi has N integers A_1, A_2, \ldots, A_N.

Given a positive integer K, determine for each of A_1, A_2, \ldots, A_N whether it is divisible by K, and find the number of integers that are divisible by K.

Here, an integer a is divisible by K means that there exists an integer q such that a = K \times q. For example, -6 is divisible by 3, and 0 is divisible by any positive integer.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq K \leq 10^9
• -10^9 \leq A_i \leq 10^9
• All inputs are integers

Sample Input 1

5 3
1 3 6 -4 0

Sample Output 1

3

Sample Input 2

6 5
1 2 3 4 6 7

Sample Output 2

0

Sample Input 3

12 7
14 -21 28 5 0 49 56 -1 70 100 -98 13

Sample Output 3

8

Sample Input 4

30 12
12 24 36 48 60 72 84 96 108 120 -12 -24 -36 -48 -60 -72 1 11 13 25 37 49 61 73 85 97 0 144 -120 1000000000

Sample Output 4

19

Sample Input 5

1 1000000000
-1000000000

Sample Output 5

1

Problem Statement

Takahashi runs an orchard. This year's harvest season lasts N days, and the weather for each day has already been determined. The weather for each day is one of "sunny," "cloudy," or "rainy," and the weather on day i is represented by W_i. W_i is S for sunny, C for cloudy, and R for rainy.

Fruit harvesting can only be done on sunny days. To hire a part-time worker, Takahashi will sign a contract that selects exactly one period of K consecutive days from the N days as the work period. That is, he chooses an integer d (1 \leq d \leq N - K + 1) and sets the work period from day d to day d + K - 1.

Takahashi wants to choose the period so that the number of sunny days included in the chosen K days is as large as possible.

Given the weather for all N days, find the maximum number of sunny days contained in any selection of K consecutive days.

Constraints

• 1 \leq K \leq N \leq 10^6
• N, K are integers.
• W_i (1 \leq i \leq N) is one of S, C, R.

Sample Input 1

7 3
S C S S R S C

Sample Output 1

2

Sample Input 2

5 3
R C R C R

Sample Output 2

0

Sample Input 3

15 5
S S C R S S S C R R S S S S C

Sample Output 3

4

Sample Input 4

30 7
S C S S R S S S C R S S S S R C S S S R S C S S S S C R S S

Sample Output 4

5

Sample Input 5

1 1
S

Sample Output 5

1

Problem Statement

Takahashi found N sweets lined up in a row at a candy shop. The weight of the i-th sweet from the left is W_i grams.

Takahashi wants to choose one or more consecutive sweets from the lineup, put them all into a single bag, and take them home.

The shop has M bags available, and the j-th bag has a weight capacity of C_j grams. Since a bag will tear if the total weight of the sweets inside exceeds its capacity, the total weight of the sweets must not exceed the capacity of the chosen bag.

Takahashi wanted to use the bag with the largest capacity so he could fit as many sweets as possible, but unfortunately that bag was sold out. In fact, the bags had been sold starting from the one with the largest capacity, and the only bag remaining was the one with the smallest capacity. Having no other choice, Takahashi decided to use that bag.

In other words, the capacity of the bag Takahashi uses is C_{\min} = \min(C_1, C_2, \ldots, C_M) grams.

Find the number of ways to choose consecutive sweets such that Takahashi can take them home without tearing the bag. Specifically, find the number of pairs of integers (l, r) satisfying 1 \leq l \leq r \leq N such that

W_l + W_{l+1} + \cdots + W_r \leq \min(C_1, C_2, \ldots, C_M)

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq M \leq 5 \times 10^5
• 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq C_j \leq 10^{18} (1 \leq j \leq M)
• All inputs are integers

Sample Input 1

5 3
1 2 3 4 5
10 20 30

Sample Output 1

12

Sample Input 2

3 2
5 5 5
3 10

Sample Output 2

0

Sample Input 3

10 5
1 1 1 1 1 1 1 1 1 1
5 8 3 7 6

Sample Output 3

27

Sample Input 4

20 10
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
100 50 30 80 25 60 45 70 35 55

Sample Output 4

83

Sample Input 5

1 1
1
1

Sample Output 5

1

Problem Statement

Takahashi is in charge of managing a flower bed. The flower bed has N flowers planted in a row, numbered flower 1, flower 2, \ldots, flower N from left to right.

Each flower has a non-negative integer value called "dryness level," and the initial dryness level of flower i is F_i. Flowers with higher dryness levels are more likely to wilt, so they need watering.

Takahashi performs M watering operations in order. In the j-th operation (j = 1, 2, \ldots, M), he waters all flowers from flower L_j to flower R_j, decreasing each of their dryness levels by D_j.

Specifically, if flower i (L_j \leq i \leq R_j) currently has a dryness level of v, this operation updates it to \max(v - D_j,\ 0). In other words, the dryness level never goes below 0.

After all watering operations are completed, flowers whose dryness level is at most the threshold T are considered to be in a "healthy state" and can continue to bloom beautifully. On the other hand, flowers whose dryness level remains greater than T are still at high risk of wilting.

Aoki looks at Takahashi's watering plan and says, "There will probably be many flowers you can't make healthy," but Takahashi is confident in his plan.

After Takahashi's plan is executed, find the number of flowers that are in a healthy state (i.e., flowers whose final dryness level is at most T).

Constraints

• 1 \leq N \leq 5 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 0 \leq T \leq 10^9
• 0 \leq F_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
• 1 \leq D_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers.

Sample Input 1

5 3 4
7 2 10 5 8
1 3 3
3 5 4
2 4 2

Sample Output 1

5

Sample Input 2

4 2 3
1 10 5 8
2 3 2
4 4 4

Sample Output 2

2

Sample Input 3

10 6 5
0 12 7 20 5 9 14 3 18 6
1 5 4
4 10 6
2 7 3
8 9 10
1 10 1
6 6 5

Sample Output 3

9

Sample Input 4

30 18 100
150 80 220 0 95 310 500 120 75 640 130 90 1000 45 260 330 10 700 85 400 55 600 140 20 900 110 70 350 480 5
1 10 50
5 15 80
12 30 60
3 3 200
18 25 300
1 30 20
7 14 100
20 30 150
2 28 10
16 16 5
1 1 1000
10 22 40
23 27 500
4 19 30
8 8 70
29 30 10
6 24 90
13 17 200

Sample Output 4

24

Sample Input 5

1 0 1000000000
1000000000

Sample Output 5

1

Problem Statement

There are N people, numbered 1 to N. Each person i initially has a non-negative integer value V_i.

Takahashi will design a "transmission network". A transmission network is defined by an array A = (A_1, A_2, \ldots, A_N) of length N, where each A_i is an integer between 1 and N (inclusive), representing the destination for person i (it is allowed that A_i = i).

Once the transmission network is determined, "transmission operations" can be performed. One transmission operation is carried out as follows:

• All people simultaneously send their current values to their destinations. That is, person i sends their pre-operation value to person A_i.
• After the operation, the new value of each person j becomes the bitwise exclusive OR (XOR) of the pre-operation values of all people who sent their values to j. That is, the new value of person j is the XOR of V_k (the pre-operation value) for all k such that A_k = j. If there is no k satisfying A_k = j, the value of person j becomes 0.

Takahashi and Aoki play a game using the following procedure:

1. Takahashi decides the array A (where each A_i is an integer between 1 and N inclusive).
2. Aoki inspects the contents of the array A, chooses exactly one person, and rewrites their initial value to an arbitrary non-negative integer. (Aoki must choose exactly one person, but rewriting to the same value as the original is allowed. In other words, he can choose to leave the value practically unchanged.)
3. The transmission operation is performed exactly K times.
4. The sum of the values of all people is calculated.

Takahashi wants to maximize this sum, and Aoki wants to minimize this sum.

Find the sum of the values of all people after K transmission operations when both players play optimally.

Notes

The bitwise exclusive OR (XOR) of non-negative integers is an operation where, when two non-negative integers are represented in binary, the result has a 1 in each digit if and only if exactly one of the two numbers has a 1 in that digit, and 0 otherwise. The XOR of multiple values is obtained by applying this operation sequentially (since it is associative, the order does not affect the result). The XOR of a single value is the value itself, and the XOR of zero values is defined as 0.

Constraints

• 1 \leq N \leq 12
• 1 \leq K \leq 10^{18}
• 0 \leq V_i \leq 10^{9}
• All input values are integers.

Sample Input 1

3 2
1 2 3

Sample Output 1

3

Sample Input 2

4 1
0 5 7 10

Sample Output 2

12

Sample Input 3

8 17
12 34 56 78 90 123 456 789

Sample Output 3

849

Sample Input 4

12 123456789012345678
1000000000 999999937 123456789 987654321 0 1 2 3 255 1024 65535 314159265

Sample Output 4

2425337132

Sample Input 5

1 1000000000000000000
1000000000

Sample Output 5

0