Problem Statement

Takahashi is exploring a dungeon.

In the dungeon, N monsters are lined up in a row, and the strength of the i-th monster is H_i. Takahashi starts with an initial health of P and fights the monsters one by one in order from the 1-st to the N-th. He cannot skip monsters or go back to fight them again.

When Takahashi fights monster i, one of the following occurs depending on his current health:

• If his current health is greater than or equal to H_i, he successfully defeats the monster, and his health decreases by H_i.
• If his current health is less than H_i, he fails to defeat the monster. In this case, the shock of the monster's counterattack instead awakens his power, and his health increases by H_i. The monster remains undefeated, and he proceeds to the next monster.

There is no upper limit on health, and even if his health becomes exactly 0 as a result of a battle, the exploration continues. Note that, due to the rules above, his health will never become negative.

After all battles with the monsters are finished, determine the number of monsters that Takahashi successfully defeated.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq P \leq 10^9
• 1 \leq H_i \leq 10^9
• All input values are integers.

Sample Input 1

5 7
3 10 4 8 2

Sample Output 1

4

Sample Input 2

4 2
5 1 10 3

Sample Output 2

2

Sample Input 3

12 20
5 7 30 10 12 1 40 8 50 20 3 60

Sample Output 3

9

Sample Input 4

20 100
20 50 40 200 30 60 10 500 100 90 80 70 60 50 400 30 20 10 1000 5

Sample Output 4

15

Sample Input 5

1 1
1

Sample Output 5

1

Problem Statement

The programming circle that Takahashi belongs to has N members. Each member has a rating, and the rating of member i is S_i.

The circle will soon be dividing into teams, and Aoki is investigating the relationships between members. Each member has a self-assessed value of their own rating, and the self-assessed value of member i is C_i. However, the self-assessed value does not necessarily match the actual rating.

Aoki wants to know how many pairs exist where one member "looks down on" another member. Member i "looks down on" member j if all of the following conditions are satisfied:

• i \neq j
• Member i's self-assessed value is strictly greater than member j's rating (i.e., C_i > S_j)
• Member i's rating is less than or equal to member j's rating (i.e., S_i \leq S_j)

In other words, this is a situation where member i is overconfident, believing their self-assessed ability exceeds the other's actual ability, despite their own actual ability being no greater than the other's.

Find the total number of ordered pairs (i, j) that are in a "looking down on" relationship. Here, when member i looks down on member j, we count (i, j) as one pair. Whether member i looks down on member j and whether member j looks down on member i are determined independently, and (i, j) and (j, i) are counted separately.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq S_i \leq 10^9
• 1 \leq C_i \leq 10^9
• All inputs are integers

Sample Input 1

4
10 15
12 11
8 20
15 15

Sample Output 1

4

Sample Input 2

3
10 5
20 10
30 30

Sample Output 2

0

Sample Input 3

10
100 150
120 130
120 200
80 90
200 250
150 150
90 300
300 100
200 199
50 1000

Sample Output 3

21

Sample Input 4

30
500 700
300 450
800 600
1000 1200
750 1000
200 900
600 601
900 950
100 1000
400 399
850 2000
650 700
700 650
950 1100
250 260
550 100
150 10000
1000 1000
350 800
450 460
50 51
999 1500
1 1000000000
1000000000 1
720 721
720 1000
880 879
330 1000
660 500
110 111

Sample Output 4

158

Sample Input 5

2
1 1000000000
999999999 1

Sample Output 5

1

Problem Statement

Takahashi has built a domino toppling course with N dominoes arranged in a line. The dominoes are numbered from 1 to N from left to right.

Each domino i (1 \leq i \leq N) has a "tolerance value" P_i and an "impact increment" D_i. The tolerance value is the maximum impact value at which the domino can fall normally without being shattered.

In this course, the domino toppling begins by hitting a ball against domino 1. Let S be the initial impact value when the ball hits. The domino toppling proceeds sequentially from domino 1 as follows.

Let C_i denote the impact value when it reaches domino i. For domino 1, C_1 = S.

• If C_i \leq P_i (the impact value is at most the tolerance value), domino i falls normally. When i < N, the fallen domino i transmits the impact to the next domino i+1, and the impact value reaching domino i+1 is C_{i+1} = C_i + D_i.
• If C_i > P_i (the impact value exceeds the tolerance value), domino i cannot withstand the impact and is shattered. A shattered domino crumbles without falling, so no impact is transmitted to the next domino, and the domino toppling ends there. A shattered domino is not considered to have "fallen normally."

Takahashi performs Q experiments. Each experiment is independent of the others, and all dominoes are reset to their initial configuration before each experiment. In each experiment j (1 \leq j \leq Q), the initial impact value S_j of the ball hitting domino 1 is given.

For each experiment, determine the number of the last domino that fell normally. If all dominoes fell normally, output N. If even domino 1 did not fall normally (i.e., S_j > P_1), output 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq D_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq S_j \leq 10^9 (1 \leq j \leq Q)
• All input values are integers.

Note

The impact value may exceed 10^9 during the domino toppling process. When all dominoes fall normally, the impact value can reach up to S_j + D_1 + D_2 + \cdots + D_{N-1}, but this fits within the range of a 64-bit signed integer.

D_N is given as input, but since there is no domino after domino N, it is not used.

Sample Input 1

3 3
5 2
6 3
20 0
3
5
6

Sample Output 1

3
1
0

Sample Input 2

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

Sample Output 2

4
4
4
0

Sample Input 3

10 6
8 5
20 0
18 4
30 10
60 0
25 2
26 8
40 1
42 3
100 0
0
5
6
8
15
1

Sample Output 3

10
10
6
5
0
10

Sample Input 4

40 20
200000000 30000000
250000000 30000000
300000000 30000000
350000000 30000000
400000000 30000000
450000000 30000000
500000000 30000000
550000000 30000000
600000000 30000000
650000000 30000000
680000000 100000000
760000000 100000000
840000000 100000000
920000000 100000000
1000000000 100000000
1000000000 100000000
1000000000 100000000
1000000000 100000000
1000000000 100000000
1000000000 0
900000000 50000000
850000000 50000000
800000000 50000000
750000000 50000000
700000000 50000000
650000000 50000000
600000000 50000000
550000000 50000000
500000000 50000000
450000000 50000000
400000000 50000000
350000000 50000000
300000000 50000000
250000000 50000000
200000000 50000000
150000000 0
120000000 0
100000000 0
80000000 0
60000000 0
0
10000000
50000000
90000000
120000000
150000000
180000000
200000000
220000000
240000000
260000000
280000000
300000000
350000000
400000000
450000000
500000000
600000000
800000000
1000000000

Sample Output 4

18
17
17
17
16
16
16
16
0
0
0
0
0
0
0
0
0
0
0
0

Sample Input 5

1 5
7 1000000000
0
7
8
1000000000
6

Sample Output 5

1
1
0
0
1

Problem Statement

Takahashi is surveying a traverse route through a mountainous region. There are N points in this mountainous region, numbered from 1 to N. The points are connected by N-1 bidirectional paths, and any two points can be reached from each other by exactly one route (i.e., they form a tree structure).

The tree structure is given by specifying the parent of each point when point 1 is the root. Specifically, the parent of point i (2 \leq i \leq N) is point p_i.

Each point i (1 \leq i \leq N) has an elevation H_i. Different points may have the same elevation.

Takahashi conducts Q route surveys. In each survey j (1 \leq j \leq Q), a starting point u_j and an ending point v_j are specified (it is possible that u_j = v_j). Consider the unique path on the tree from point u_j to point v_j. Let the points on this path, listed in order from u_j to v_j, be a_1, a_2, \ldots, a_k. Here, k is the number of points on the path, with a_1 = u_j and a_k = v_j. When u_j = v_j, we have k = 1 and a_1 = u_j.

The elevation sequence corresponding to this path is defined as h_1, h_2, \ldots, h_k, where h_t = H_{a_t} for each t (1 \leq t \leq k).

For each survey, find the length of the longest strictly decreasing subsequence of this elevation sequence.

Definitions

• A subsequence of a sequence h_1, h_2, \ldots, h_k is a sequence obtained by choosing a set of indices (m \geq 1) satisfying 1 \leq i_1 < i_2 < \cdots < i_m \leq k, and listing h_{i_1}, h_{i_2}, \ldots, h_{i_m} in their original order. The chosen indices do not need to be consecutive in the original sequence.
• A strictly decreasing subsequence is a subsequence h_{i_1}, h_{i_2}, \ldots, h_{i_m} of length m \geq 1 (1 \leq i_1 < i_2 < \cdots < i_m \leq k) satisfying h_{i_1} > h_{i_2} > \cdots > h_{i_m}. In particular, when m = 1, this condition is automatically satisfied.
• The length of the longest strictly decreasing subsequence is the maximum length m among all strictly decreasing subsequences. Since a subsequence of length 1 always exists when k \geq 1, the length of the longest strictly decreasing subsequence is always at least 1.

Constraints

• 1 \leq N \leq 5000
• 1 \leq Q \leq 5000
• 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq p_i \leq i - 1 (2 \leq i \leq N)
• 1 \leq u_j, v_j \leq N (1 \leq j \leq Q)
• All input values are integers.

Sample Input 1

5 4
10 30 20 40 5
1 1 2 2
4 3
4 5
1 1
3 4

Sample Output 1

3
3
1
2

Sample Input 2

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

Sample Output 2

1
1
1
1
1

Sample Input 3

10 8
100 80 90 60 70 50 40 30 20 10
1 1 2 2 3 3 4 4 5
7 9
1 10
10 7
4 6
8 9
3 2
5 6
1 1

Sample Output 3

4
4
3
3
2
2
3
1

Sample Input 4

20 15
50 40 60 30 70 20 80 10 90 5 55 45 65 35 75 25 85 15 95 1
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
15 16
1 20
7 18
3 2
11 14
20 19
9 10
13 12
17 8
5 6
1 1
19 20
4 15
6 11
2 9

Sample Output 4

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

Sample Input 5

1 1
1000000000

1 1

Sample Output 5

1

Problem Statement

Takahashi is in charge of dividing N students into research groups as the coordinator of a university laboratory. The students are numbered from 1 to N.

Each student i has a "specialization score" W_i. Two students i and j (i \neq j) are defined to be "compatible" if and only if \gcd(W_i, W_j) \geq K. Here, \gcd denotes the greatest common divisor.

The formation of the research groups must follow these rules:

• Any two students belonging to the same group must be directly or indirectly connected through "compatible" relationships. Specifically, for any two students a and b in the same group, there must exist a sequence of students a = p_1, p_2, \ldots, p_m = b such that all adjacent pairs p_k and p_{k+1} are "compatible" pairs.
• Conversely, students who are directly or indirectly connected through "compatible" relationships must belong to the same group.

In other words, the set of students in each group corresponds to a connected component determined by the "compatible" relationship.

Takahashi calls the sum of the specialization scores of the students in each group the "total strength" of that group. Find the maximum total strength among all groups.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^6
• 1 \leq W_i \leq 10^6
• All input values are integers.

Sample Input 1

6 3
6 10 15 7 22 25

Sample Output 1

56

Sample Input 2

4 10
2 3 5 7

Sample Output 2

7

Sample Input 3

18 6
12 18 25 35 49 77 22 33 55 65 91 14 26 39 52 64 96 160

Sample Output 3

558

Sample Input 4

50 50000
100000 200000 300000 400000 500000 600000 700000 800000 900000 1000000 99991 199982 299973 399964 499955 599946 699937 799928 899919 999910 65536 131072 196608 262144 327680 393216 458752 524288 589824 655360 70001 140002 210003 280004 350005 420006 490007 560008 630009 700010 1 2 3 49999 50021 75011 99989 123457 234567 345679

Sample Output 4

5500000

Sample Input 5

1 1000000
1

Sample Output 5

1