Problem Statement

Takahashi and Aoki each took notes during the same lecture. However, both of them had parts they couldn't read, so their notes contain some blanks.

The content written on the blackboard during the lecture was a string of N characters consisting only of lowercase English letters. Let string S represent Takahashi's notes and string T represent Aoki's notes. Both S and T consist of N characters, where parts that couldn't be read are recorded as ?. All other parts are recorded as lowercase English letters, but due to copying errors, some characters may differ from the original blackboard content.

The two compare each other's notes and attempt to reconstruct the original blackboard content. They decide to trust characters that both of them wrote down identically. For each position i (1 \leq i \leq N), they compare the i-th character of S with the i-th character of T and determine the i-th character of the reconstruction according to the following rules:

• If both are the same lowercase English letter, adopt that letter.
• If one is ? and the other is a lowercase English letter, adopt that lowercase English letter.
• If both are ?, the character cannot be reconstructed, so it remains ?.
• If both are lowercase English letters but differ from each other, at least one of the notes contains a copying error and the correct character cannot be determined, so it becomes ! to represent a contradiction.

Output the resulting string after performing the reconstruction for all positions. Also, determine whether the reconstruction result contains at least one contradiction (!), and output Yes if it does, or No if it does not.

Constraints

• 1 \leq N \leq 5 \times 10^5
• N is an integer.
• S is a string of length N consisting of lowercase English letters and ?.
• T is a string of length N consisting of lowercase English letters and ?.

Sample Input 1

5
ab?de
a?cd?

Sample Output 1

abcde
No

Sample Input 2

6
abc?ef
axc?yf

Sample Output 2

a!c?!f
Yes

Sample Input 3

15
he??o?wor?d?abc
?ell??world?axc

Sample Output 3

hello?world?a!c
Yes

Sample Input 4

40
ab?dab?dab?dab?dab?dab?dab?dab?dab?dab?d
a?cda?cda?cda?cda?cda?cda?cda?cda?cda?cd

Sample Output 4

abcdabcdabcdabcdabcdabcdabcdabcdabcdabcd
No

Sample Input 5

1
?
?

Sample Output 5

?
No

Problem Statement

Takahashi manages N flower beds arranged in a row in his garden. The flower beds are numbered 1 to N from left to right, and flower bed i has a defined "beauty" value A_i.

For each of the N flower beds, Takahashi chooses whether or not to maintain it. However, the selection of flower beds to maintain must satisfy the following condition:

• There exists an integer l (1 \leq l \leq N - K + 1) such that flower beds l, l+1, \ldots, l+K-1 are all included in the maintained flower beds.

In other words, there must exist at least one interval where K consecutive flower beds are all maintained. As long as this condition is satisfied, any other flower bed may or may not be maintained.

Find the maximum possible sum of beauty values of the flower beds chosen for maintenance.

Constraints

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

Sample Input 1

5 2
3 -5 4 2 -1

Sample Output 1

9

Sample Input 2

4 3
-2 -7 -1 -3

Sample Output 2

-10

Sample Input 3

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

Sample Output 3

25

Sample Input 4

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

Sample Output 4

54

Sample Input 5

1 1
-1000000000

Sample Output 5

-1000000000

Problem Statement

Takahashi manages N smartphones. The smartphones are numbered from 1 to N, and the initial battery level of smartphone i (1 \leq i \leq N) is S_i.

These smartphones consume battery by receiving app notifications. One day, Q notification events occurred in order from the 1-st to the Q-th. In the j-th (1 \leq j \leq Q) notification event, the battery level of every smartphone whose number is between L_j and R_j inclusive decreases by 1. However, a smartphone whose battery level is 0 remains at 0. That is, if the battery level of a smartphone targeted by the notification event is b, then b changes to \max(b - 1,\ 0).

Find the final battery level of each smartphone after all notification events have finished.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
• All inputs are integers

Sample Input 1

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

Sample Output 1

9 3 0 6 1

Sample Input 2

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

Sample Output 2

0 0 1 0

Sample Input 3

10 8
100 0 5 20 3 15 8 0 12 7
1 5
3 7
2 6
5 10
1 10
6 8
4 4
1 3

Sample Output 3

97 0 0 15 0 10 4 0 10 5

Problem Statement

Takahashi is a mountaineer whose hobby is mountain traversing. In a certain mountainous region, there are N mountain huts, numbered from 1 to N. The mountain huts are connected by M one-way mountain trails. The j-th trail allows one-way passage from mountain hut U_j to mountain hut V_j, and cannot be traversed in the reverse direction.

Each mountain hut i has an elevation P_i. All mountain huts have distinct elevations.

Takahashi starts from mountain hut 1 and performs a traverse by following mountain trails. A sequence of mountain huts v_1, v_2, \ldots, v_k (k \geq 1) is called a "good traverse" if it satisfies all of the following conditions:

• v_1 = 1. That is, the traverse starts from mountain hut 1.
• For all i (1 \leq i \leq k-1), there exists a one-way mountain trail from mountain hut v_i to mountain hut v_{i+1}.
• For all i (1 \leq i \leq k-1), P_{v_i} < P_{v_{i+1}} holds. That is, the elevations of consecutively visited mountain huts are strictly monotonically increasing.

A "good traverse" may end at any mountain hut; there is no constraint on the endpoint. Additionally, staying only at mountain hut 1 without following any trail (k = 1) also counts as a "good traverse". Therefore, the answer is always at least 1.

Takahashi wants to visit as many mountain huts as possible. Find the maximum value of k, the number of mountain huts visited in a "good traverse".

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
• All P_i are distinct.
• 1 \leq U_j, V_j \leq N (1 \leq j \leq M)
• U_j \neq V_j (1 \leq j \leq M)
• The same pair (U_j, V_j) is not given more than once.
• All input values are integers.

Sample Input 1

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

Sample Output 1

4

Sample Input 2

4 4
100 50 30 200
1 2
1 3
2 4
3 4

Sample Output 2

1

Sample Input 3

8 9
15 30 10 45 25 50 35 60
1 2
1 5
2 4
5 7
7 4
4 6
6 8
1 3
3 5

Sample Output 3

6

Sample Input 4

15 20
5 50 10 45 15 40 20 35 25 30 55 60 65 70 75
1 3
3 5
5 7
7 9
9 10
10 11
11 12
12 13
13 14
14 15
1 2
2 4
4 6
6 8
1 5
3 7
5 9
9 11
7 10
2 6

Sample Output 4

11

Sample Input 5

1 0
1000000000

Sample Output 5

1

Problem Statement

Takahashi is a chaperone for a school field trip. The field trip uses N buses, numbered from Bus 1 to Bus N. Bus i has S_i boxed lunches loaded on it, and P_i students are riding in it.

When lunchtime comes, each student on every bus must receive exactly 1 boxed lunch. Since boxed lunches cannot be transferred between buses, the condition for all students on Bus i to receive a lunch is S_i \geq P_i. Having leftover lunches is not a problem.

For the field trip plan, M rest stop plans have been proposed. In rest stop plan j, buses with consecutive numbers from Bus L_j to Bus R_j stop together at a rest area to have lunch.

Rest stop plan j is said to be distributable if S_i \geq P_i holds for every bus i satisfying L_j \leq i \leq R_j. Conversely, if there exists even one bus i with L_j \leq i \leq R_j such that S_i < P_i, the plan is not distributable.

For each rest stop plan, determine whether it is distributable or not.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq S_i \leq 10^9 （ 1 \leq i \leq N ）
• 0 \leq P_i \leq 10^9 （ 1 \leq i \leq N ）
• 1 \leq L_j \leq R_j \leq N （ 1 \leq j \leq M ）
• All input values are integers.

Sample Input 1

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

Sample Output 1

No
No
No

Sample Input 2

4 5
5 0 3 10
5 1 3 10
1 1
1 4
2 2
2 3
4 4

Sample Output 2

Yes
No
No
No
Yes

Sample Input 3

10 8
100 50 30 20 60 10 45 80 25 70
90 50 35 15 60 10 40 85 20 65
1 10
1 5
3 3
4 6
6 6
7 9
5 8
1 3

Sample Output 3

No
No
No
Yes
Yes
No
No
No