Problem Statement

Takahashi worked N different part-time jobs this month.

The hourly wage of the i-th job is A_i yen, and Takahashi worked T_i hours at that job.

Find the total salary (in yen) that Takahashi will receive this month.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^6
• 1 \leq T_i \leq 10^6
• All input values are integers

Sample Input 1

3
1000 5
1200 3
900 4

Sample Output 1

12200

Sample Input 2

2
850 1
1500 2

Sample Output 2

3850

Sample Input 3

7
980 12
1250 8
1500 6
1100 10
2000 3
950 15
1750 4

Sample Output 3

69010

Sample Input 4

15
1000 40
1200 35
950 28
1500 20
1300 22
1600 18
1100 30
1750 16
1400 25
2000 12
1050 27
1800 14
1550 19
900 33
1450 21

Sample Output 4

459150

Sample Input 5

1
1000000 1000000

Sample Output 5

1000000000000

Problem Statement

Takahashi and Aoki are serving as judges for a cooking contest. In this contest, N participants each submit one dish, and the two judges assign a score to every dish.

The participants are numbered from 1 to N. Let A_i be the score that Takahashi gives to participant i's dish, and B_i be the score that Aoki gives to participant i's dish. Each score is an integer between 1 and 100, inclusive.

Each participant's final score is determined by the sum of Takahashi's score and Aoki's score, A_i + B_i. The participant with the highest final score wins. It is guaranteed that there is exactly one participant with the highest final score.

Find the participant number of the winner.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 100 (1 \leq i \leq N)
• 1 \leq B_i \leq 100 (1 \leq i \leq N)
• All inputs are integers.
• There is exactly one participant with the highest final score.

Sample Input 1

3
50 60
80 70
40 90

Sample Output 1

2

Sample Input 2

5
10 20
30 40
50 50
60 30
20 70

Sample Output 2

3

Sample Input 3

10
45 55
60 40
30 70
80 15
25 75
50 50
90 10
35 65
70 30
55 46

Sample Output 3

10

Sample Input 4

20
12 34
56 78
90 11
23 45
67 89
1 99
100 50
48 52
73 27
36 64
85 14
29 71
58 42
17 83
94 5
41 59
66 33
8 91
75 25
53 47

Sample Output 4

5

Sample Input 5

1
1 1

Sample Output 5

1

Problem Statement

Takahashi is a system administrator at a company. The company has N types of resources, and each resource has a set of required permissions to access it. Permissions consist of L permission items, and the permissions required for the i-th resource are represented by a bit string S_i of length L. A bit string is a string consisting of 0 and 1, where the leftmost bit is the most significant bit (MSB). When the p-th bit (1 \leq p \leq L, counting the leftmost bit as the 1st bit) of the bit string is 1, it means that the p-th permission item is required to access that resource.

The access permissions granted to an employee are also represented by a bit string K of length L. The condition for an employee to access resource i is that the employee possesses all permission items required by that resource. In other words, for each bit position, if the bit of S_i is 1, then the bit at the same position in K must also be 1 (i.e., the bitwise AND satisfies K \mathbin{\&} S_i = S_i).

Aoki is the company's security officer and promotes a policy of not granting unnecessarily broad permissions. Aoki has given Takahashi Q requests. In the j-th request (1 \leq j \leq Q), the numbers of M_j resources that a certain employee needs to access are specified: c_{j,1}, c_{j,2}, \ldots, c_{j,M_j} (resource numbers may be duplicated within the same request). Among all permission bit strings K that allow access to all specified resources, find the one whose value is minimized when the bit string is interpreted as a binary number.

Note that a permission bit string that allows access to all specified resources always exists (for example, a bit string with all bits set to 1 satisfies the condition).

Constraints

• 1 \leq N \leq 10^5
• 1 \leq L \leq 64
• 1 \leq Q \leq 10^5
• S_i is a string of length L consisting of 0 and 1 (1 \leq i \leq N)
• M_j is the number of resources specified in the j-th request, and 1 \leq M_j \leq N (1 \leq j \leq Q)
• c_{j,k} is a resource number specified in the j-th request, and 1 \leq c_{j,k} \leq N (1 \leq j \leq Q, 1 \leq k \leq M_j)
• Resource numbers may be duplicated within the same request
• \sum_{j=1}^{Q} M_j \leq 10^5
• S_i is given as a string; all other inputs are integers

Sample Input 1

3 4 3
1010
0110
1001
1 1
2 1 2
3 1 2 3

Sample Output 1

1010
1110
1111

Sample Input 2

5 8 4
10100000
01010000
00001010
00000101
11000011
1 3
2 1 3
3 2 4 5
4 1 2 3 4

Sample Output 2

00001010
10101010
11010111
11111111

Sample Input 3

6 16 5
1000000000000001
0100000000000010
0010000000000100
0001000000001000
0000100000010000
1111100000000000
2 1 2
3 1 3 5
1 6
4 2 3 4 5
6 1 2 3 4 5 6

Sample Output 3

1100000000000011
1010100000010101
1111100000000000
0111100000011110
1111100000011111

Problem Statement

Takahashi is the leader of a group consisting of N members. The members are numbered from 1 to N, and the skill value of member i (1 \le i \le N) is A_i.

Takahashi wants to divide this group into two teams at a boundary of consecutive numbers. Specifically, he chooses an integer k (1 \le k < N), and assigns members 1 through k to "Team A" and members k+1 through N to "Team B".

Let the sum of skill values of Team A be S_1 = A_1 + A_2 + \cdots + A_k, and the sum of skill values of Team B be S_2 = A_{k+1} + A_{k+2} + \cdots + A_N.

Find the minimum value of |S_1 - S_2| when k is chosen optimally.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

4
1 2 3 4

Sample Output 1

2

Sample Input 2

5
1 3 2 2 4

Sample Output 2

0

Sample Input 3

15
8 1 6 3 5 7 4 9 2 10 12 11 14 13 15

Sample Output 3

10

Sample Input 4

40
17 23 5 11 29 31 7 13 19 2 37 41 3 43 47 53 59 61 67 71 73 79 83 89 97 101 107 109 113 127 131 137 139 149 151 157 163 167 173 179

Sample Output 4

71

Sample Input 5

2
1000000000 1000000000

Sample Output 5

0

Problem Statement

Takahashi is looking at a landscape where N mountains are lined up in a row. Each mountain is numbered from 1 to N, and mountain i has an elevation of A_i meters.

For each mountain, Takahashi wants to find out "how many other mountains have a strictly higher elevation." This serves as a reference for understanding how many mountains taller than himself exist when standing at the summit of that mountain.

For each of the N mountains, determine the number of other mountains that have a strictly higher elevation.

Constraints

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

Sample Input 1

5
3 1 4 1 5

Sample Output 1

2 3 1 3 0

Sample Input 2

8
100 200 150 200 300 100 250 300

Sample Output 2

6 3 5 3 0 6 2 0

Sample Input 3

12
1000000000 1 500000000 999999999 1000000000 250000000 750000000 1 999999998 500000000 250000000 750000001

Sample Output 3

0 10 6 2 0 8 5 10 3 6 8 4

Problem Statement

Takahashi is analyzing the sales data of N stores in a shopping district. The stores in the shopping district are numbered from 1 to N, and the daily sales of each store i is V_i yen.

The shopping district is planning a campaign to designate contiguous stores as a "sales promotion area." A sales promotion area is defined by choosing a pair of integers (l, r) (1 \leq l \leq r \leq N) and including all consecutive stores from number l to number r. Different pairs (l, r) are considered distinct areas.

However, to ensure sufficient campaign effectiveness, only areas where the total sales of the selected stores is at least K yen will be adopted. That is, the condition V_l + V_{l+1} + \cdots + V_r \geq K must be satisfied.

Takahashi wants to know how many possible sales promotion areas can be adopted. Find the number of pairs (l, r) that satisfy the condition.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^{14}
• 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers

Sample Input 1

5 10
3 1 4 1 5

Sample Output 1

3

Sample Input 2

8 15
5 3 8 2 7 4 6 1

Sample Output 2

18

Sample Input 3

10 1000000000000
100000000 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 1000000000

Sample Output 3

0

Problem Statement

There are N students in Takahashi's class. The students are assigned attendance numbers from 1 to N.

In this class, some pairs of students are friends with each other. There are M friendship relations, and the j-th friendship is between student U_j and student V_j. Friendships are bidirectional, and students who are connected directly or indirectly through friendships are considered to belong to the same group.

One day, the teacher contacted specific students to convey announcements to the class. A student who receives the contact shares the announcement with everyone in the same group.

The teacher made Q contacts, and in the k-th contact, the teacher contacted student S_k.

Takahashi wants to know how many students actually received the announcement for each contact. For each contact, find the total number of students who received the announcement.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
• If i \neq j, then (U_i, V_i) \neq (U_j, V_j)
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq S_k \leq N (1 \leq k \leq Q)
• All inputs are integers

Sample Input 1

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

Sample Output 1

3
2
3

Sample Input 2

6 2
1 3
2 4
4
1
5
2
6

Sample Output 2

2
1
2
1

Sample Input 3

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

Sample Output 3

4
3
2
1
3

Sample Input 4

15 10
1 2
2 3
3 4
4 5
6 7
7 8
9 10
10 11
11 12
13 14
8
1
6
9
13
15
5
8
12

Sample Output 4

5
3
4
2
1
5
3
4

Sample Input 5

1 0
1
1

Sample Output 5

1

Problem Statement

Takahashi is a surveyor for a certain region. This region contains N cities, numbered from 1 to N. The cities are connected by one-way roads, and there are M roads in total. Road j is a one-way road from city U_j to city V_j, allowing direct travel from city U_j to city V_j (travel in the reverse direction is not possible).

Each city has a distinct importance value assigned to it. The importance of city i is B_i. B_1, B_2, \ldots, B_N is a permutation of the integers from 1 to N.

Takahashi surveys all cities by repeating the following procedure. Initially, all cities are unsurveyed.

1. Determine the starting city. For the first tour, the starting city is city 1. For each subsequent tour, the starting city is the unsurveyed city with the highest importance.
2. Conduct a tour from the starting city. First, mark the starting city as surveyed. Then, repeat the following operation:

• If there exists at least one unsurveyed city among the cities directly reachable by a single road from the current city, move to the one with the highest importance among them, and mark that city as surveyed.
• If there are no unsurveyed cities among the cities directly reachable by a single road from the current city (including the case where no reachable cities exist at all), end this tour.

1. If all cities have been surveyed, stop. Otherwise, return to step 1.

Output, in order from first to last, the sequence in which Takahashi marks cities as surveyed.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq B_i \leq N
• B_1, B_2, \ldots, B_N are all distinct
• 1 \leq U_j \leq N
• 1 \leq V_j \leq N
• U_j \neq V_j
• The same pair (U_j, V_j) is not given more than once
• All input values are integers

Sample Input 1

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

Sample Output 1

1 2 4 3 5

Sample Input 2

4 0
2 4 3 1

Sample Output 2

1 2 3 4

Sample Input 3

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

Sample Output 3

1 4 6 7 8 2 3 5

Sample Input 4

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

Sample Output 4

1 2 3 4 5 6 7 8 9 10

Sample Input 5

1 0
1

Sample Output 5

1

Problem Statement

N children are standing in a circle playing a game. The children are numbered 1 to N in clockwise order, and the clockwise neighbor of child N is child 1.

Initially, all children are participating in the circle, and child number S is holding the ball.

M passes will be performed. For the i-th pass, let x be the child currently holding the ball, and the following operation is performed:

1. Starting from the position clockwise next to x, count only the children still remaining in the circle (excluding x itself) in clockwise order as 1, 2, 3, \ldots. Children who have already left the circle are skipped. If the count exceeds the number of remaining children, continue counting by going around the circle as many times as needed.
2. Pass the ball to the child counted as the D_i-th.
3. Immediately after, x leaves the circle. In subsequent passes, x will neither be counted nor receive the ball.

After all M passes have been completed, output the number of the child holding the ball.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq N - 1
• 1 \leq S \leq N
• 1 \leq D_i \leq 10^9
• All inputs are integers

Sample Input 1

5 3 1
1
2
1

Sample Output 1

5

Sample Input 2

6 4 3
5
1
7
2

Sample Output 2

1

Sample Input 3

20 10 8
3
15
1
22
7
100
4
9
18
2

Sample Output 3

19

Sample Input 4

60 30 60
1
59
123456789
17
42
1000000000
8
31
73
2
500
19
64
27
91
6
38
111
25
3
999999937
14
52
7
86
41
12
68
29
5

Sample Output 4

17

Sample Input 5

2 1 2
1000000000

Sample Output 5

1

Problem Statement

Takahashi is in charge of managing a road network consisting of N cities.

This network has the structure of a rooted tree, with city 1 being the capital (root). Each city i (2 \leq i \leq N) has a designated parent city P_i (P_i < i), and there exists exactly one road directly connecting city i and its parent city P_i. We will call this road road i. Road i has a durability value representing its resistance to traffic load, with an initial durability value of W_i. There are N - 1 roads in total, and since the structure is a tree, the path (a sequence of roads not passing through the same city twice) connecting any two cities is uniquely determined.

Takahashi performs Q reinforcement operations on the roads. In the j-th (1 \leq j \leq Q) reinforcement operation, he specifies two cities u_j, v_j and increases the durability value of every road on the path connecting city u_j and city v_j by 1. If u_j = v_j, there are no roads on the path, so nothing changes. The same road may have multiple reinforcement operations applied to it, and each time its durability value is incremented by 1.

After all Q reinforcement operations are completed, Aoki asks R questions about the state of the road network. In the k-th (1 \leq k \leq R) question, he specifies two cities a_k, b_k and asks for the minimum value among the durability values of all roads on the path connecting city a_k and city b_k. However, if a_k = b_k, there are no roads on the path, so the answer is 0.

Answer each question based on the road network after all reinforcement operations have been performed.

Constraints

• 1 \leq N \leq 5 \times 10^4
• 1 \leq P_i \leq i - 1 (2 \leq i \leq N)
• 0 \leq W_i \leq 10^9 (2 \leq i \leq N)
• 1 \leq Q \leq 5 \times 10^4
• 1 \leq u_j, v_j \leq N (1 \leq j \leq Q)
• 1 \leq R \leq 5 \times 10^4
• 1 \leq a_k, b_k \leq N (1 \leq k \leq R)
• All input values are integers.
• It is guaranteed that the answer to each question is at most 2^{63} - 1.

Sample Input 1

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

Sample Output 1

4
4
0
4

Sample Input 2

3
1 1000000000
1 0
2
2 3
1 1
3
2 3
1 2
3 3

Sample Output 2

1
1000000001
0

Sample Input 3

12
1 7
1 2
2 9
2 4
3 6
3 1
4 8
4 3
6 5
6 0
7 10
8
8 5
10 12
9 11
2 7
1 8
3 3
4 10
12 5
7
8 12
9 5
11 7
1 10
6 6
2 12
4 11

Sample Output 3

4
4
1
6
0
4
1

Sample Input 4

25
1 100
1 50
2 70
2 30
3 80
3 60
4 20
4 90
5 10
5 40
6 55
6 65
7 75
7 85
8 15
8 25
9 35
10 45
11 5
12 95
13 0
14 110
15 120
18 33
22
16 25
20 21
22 24
17 19
1 25
8 15
10 14
23 5
12 12
2 18
3 20
21 24
16 17
25 22
11 13
4 7
19 24
1 1
18 20
6 25
14 22
9 23
18
16 24
20 22
1 25
12 23
17 17
2 15
19 21
25 24
8 18
10 11
3 22
5 23
6 14
7 21
11 25
1 1
4 20
13 24

Sample Output 4

17
3
37
57
0
61
13
37
23
13
3
38
69
57
37
0
8
69

Sample Input 5

1
1
1 1
1
1 1

Sample Output 5

0

Problem Statement

Takahashi is planning to rent consecutive sections of a shopping street to set up an event venue.

The shopping street has N sections lined up in a row from left to right.

The rent for the i-th section from the left (1 \leq i \leq N) is A_i yen.

Also, for the i-th section from the left, C_i = 1 if it has a parking space, and C_i = 0 if it does not.

Takahashi is considering renting exactly K consecutive sections.

That is, he chooses an integer l (1 \leq l \leq N-K+1) and rents the K sections from the l-th to the (l+K-1)-th from the left.

Q operations will be performed in order. The j-th operation (1 \leq j \leq Q) is determined by the integer T_j and is one of the following:

• T_j = 1 (rent change): Integers X_j, Y_j are given. Change the rent of the X_j-th section from the left to Y_j yen. This change affects all subsequent operations.
• T_j = 2 (query): An integer X_j is given. Among all ways to choose exactly K consecutive sections, consider those where the chosen K sections contain at least X_j sections with parking spaces (sections where C_i = 1). If such a choice exists, output the minimum possible total rent of the chosen K sections. If no such choice exists, output IMPOSSIBLE.

Note that the values C_i representing the presence or absence of parking spaces do not change through operations.

For each operation with T_j = 2, output the answer.

Constraints

• 1 \leq K \leq N \leq 10^5
• 1 \leq Q \leq 5 \times 10^4
• 1 \leq A_i \leq 10^9
• C_i \in \{0, 1\}
• T_j \in \{1, 2\}
• When T_j = 1: 1 \leq X_j \leq N, 1 \leq Y_j \leq 10^9
• When T_j = 2: 0 \leq X_j \leq K, Y_j = 0
• There is at least one operation with T_j = 2
• All inputs are integers

Sample Input 1

5 3 5
10 20 5 7 8
1 0 1 0 1
2 1 0
2 2 0
1 2 1
2 1 0
2 2 0

Sample Output 1

20
20
13
16

Sample Input 2

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

Sample Output 2

IMPOSSIBLE
IMPOSSIBLE

Sample Input 3

12 4 10
15 3 22 8 7 13 5 19 11 2 17 6
1 0 1 1 0 0 1 0 1 1 0 1
2 2 0
2 3 0
1 5 4
2 2 0
1 10 20
2 1 0
1 1 30
2 4 0
1 8 1
2 3 0

Sample Output 3

33
36
30
30
IMPOSSIBLE
37

Sample Input 4

25 7 20
31 12 45 7 23 18 60 5 14 39 27 8 50 16 22 41 9 33 11 28 6 19 35 24 10
1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1
2 3 0
2 5 0
1 7 4
2 4 0
1 14 3
2 2 0
1 1 100
2 5 0
1 20 2
2 1 0
1 25 70
2 6 0
1 12 1
2 4 0
1 18 55
2 3 0
1 9 40
2 0 0
1 4 9
2 5 0

Sample Output 4

133
179
110
110
166
107
IMPOSSIBLE
110
108
114
181

Sample Input 5

1 1 5
1000000000
0
2 0 0
2 1 0
1 1 1
2 0 0
2 1 0

Sample Output 5

1000000000
IMPOSSIBLE
1
IMPOSSIBLE

Problem Statement

Takahashi is managing the schedule of stage presentations for a school festival. Here, we only consider the start time of each presentation, and the duration of the presentations is not considered.

There are N presenters. Presenter i (1 \leq i \leq N) has two candidate start times for their presentation: either starting at time A_i minutes, or delaying it by exactly D_i minutes to start at time A_i + D_i minutes.

Takahashi decides whether to delay the presentation for each presenter. This decision is represented by a string S of length N consisting only of 0 and 1.

• When S_i = 0, presenter i starts their presentation at time A_i minutes.
• When S_i = 1, presenter i starts their presentation at time A_i + D_i minutes.

Additionally, we are given M pairs of presenters whose presentation start times should be as far apart as possible because they share some audience members. The j-th pair (1 \leq j \leq M) consists of presenter U_j and presenter V_j.

For a string S, we define f(S) as follows:

• For each pair j (1 \leq j \leq M), calculate the absolute difference between the actual start time of presenter U_j and the actual start time of presenter V_j. The minimum of these absolute differences is f(S).

Takahashi's goal is to maximize f(S). Let K be the maximum value of f(S). Find the following:

1. The value of K
2. The lexicographically smallest string S that achieves f(S) = K.

Here, the lexicographical comparison of strings is performed with 0 < 1.

Constraints

• 1 \leq N \leq 2000
• 1 \leq M \leq 5000
• N \times M \leq 10^6
• 0 \leq A_i \leq 10^9
• 1 \leq D_i \leq 10^9
• 1 \leq U_j, V_j \leq N
• U_j \neq V_j
• All pairs (U_j, V_j) are unique, regardless of order.
• All input values are integers.

Sample Input 1

3 2
10 5
12 10
30 3
1 2
2 3

Sample Output 1

11
011

Sample Input 2

4 4
0 10
10 5
18 2
25 10
1 2
2 3
3 4
1 4

Sample Output 2

10
0011

Sample Input 3

8 10
5 7
20 4
13 15
40 10
0 30
55 5
25 20
70 8
1 2
1 3
2 4
3 4
3 5
4 6
5 7
6 8
2 7
1 8

Sample Output 3

12
00100010

Sample Input 4

15 25
100 30
150 20
80 100
300 40
260 75
400 10
50 200
500 60
620 80
700 25
710 90
900 100
850 30
1000 150
1100 50
1 2
1 3
1 7
2 3
2 4
2 8
3 5
3 7
4 5
4 6
4 9
5 6
5 10
6 8
6 11
7 8
7 12
8 9
8 13
9 10
9 14
10 11
11 15
12 13
14 15

Sample Output 4

40
110000100010000

Sample Input 5

2 1
0 1000000000
1000000000 1000000000
1 2

Sample Output 5

2000000000
01

Problem Statement

Takahashi and Aoki are trying to deduce N hidden integers A_1, A_2, \ldots, A_N.

Each A_i is an integer between 0 and K - 1 inclusive, but the specific values are unknown to both of them.

The score of an interval [L, R] is defined as the following value:

(A_L + A_{L+1} + \cdots + A_R) \bmod K

The two manage their deduction records as "versions" of a note.

Each operation references an existing version and produces a new version as its result. This causes versions to branch out in a tree structure.

Initially, there exists version 0, which contains no accepted records.

Q operations are given in order.

In the i-th operation (1 \leq i \leq Q), an already existing version B (0 \leq B \leq i - 1) is referenced, and a new version i is created as the result of the operation.

There are two types of operations:

• Type 0: 0 B L R X

Aoki claims, with respect to version B, that "the score of interval [L, R] is X."

If there exists an assignment (A_1, A_2, \ldots, A_N) where each element is an integer between 0 and K-1 inclusive that simultaneously satisfies all records accepted in version B and this claim, then accept this claim and output YES. In this case, version i consists of the accepted records of version B plus this claim.

If no such assignment exists, reject this claim and output NO. In this case, version i has the same content as version B.

• Type 1: 1 B L R

Takahashi asks whether the score of interval [L, R] can be uniquely determined from only the records accepted in version B.

If, for every assignment (A_1, A_2, \ldots, A_N) (where each element is an integer between 0 and K-1 inclusive) that satisfies all accepted records of version B, the score of interval [L, R] is the same value, then output that value.

If it cannot be uniquely determined, output UNKNOWN.

This operation does not add any new records, and version i has the same content as version B.

Process the Q operations in order and output the answer to each operation.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq K \leq 10^9
• 1 \leq Q \leq 10^5
• In the i-th operation (1 \leq i \leq Q), 0 \leq B \leq i - 1
• In each operation, 1 \leq L \leq R \leq N
• In type 0 operations, 0 \leq X \leq K - 1
• All inputs are integers

Sample Input 1

4 5 8
1 0 1 2
0 0 1 2 3
1 2 1 2
0 2 3 4 4
1 4 1 4
0 2 1 4 1
1 6 3 4
1 4 3 4

Sample Output 1

UNKNOWN
YES
3
YES
2
YES
3
4

Sample Input 2

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

Sample Output 2

YES
YES
YES
NO
5
NO
YES

Sample Input 3

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

Sample Output 3

YES
YES
9
YES
UNKNOWN
YES
7
NO
9
YES
2
NO
1
YES
UNKNOWN
YES
YES
1

Sample Input 4

20 1000000000 30
0 0 1 10 123456789
0 1 11 20 987654321
1 2 1 20
0 2 5 15 555555555
1 4 1 4
0 4 1 4 222222222
1 6 5 10
1 6 11 15
0 6 16 20 333333333
0 6 16 20 333333334
1 10 16 20
0 4 1 4 111111111
1 12 5 10
0 12 11 15 123456789
0 0 3 18 700000000
1 15 1 20
0 15 1 2 100000000
0 17 19 20 200000000
1 18 1 20
0 18 1 20 0
0 18 1 20 1
1 21 3 18
0 6 7 14 444444444
1 23 1 15
0 23 1 15 777777777
0 23 1 15 777777778
1 26 1 15
0 12 16 20 333333333
0 12 16 20 444444444
1 29 1 20

Sample Output 4

YES
YES
111111110
YES
UNKNOWN
YES
901234567
654320988
YES
NO
333333333
YES
12345678
NO
YES
UNKNOWN
YES
YES
0
YES
NO
700000000
YES
777777777
YES
NO
777777777
NO
YES
111111110

Sample Input 5

1 2 8
1 0 1 1
0 0 1 1 0
1 2 1 1
0 2 1 1 1
1 4 1 1
0 0 1 1 1
1 6 1 1
0 6 1 1 1

Sample Output 5

UNKNOWN
YES
0
NO
0
YES
1
YES

Problem Statement

Takahashi is analyzing stock price data for a certain stock over N days. The stock price on day i is H_i yen.

Takahashi wants to correct this stock price data into an ideal dataset that is "strictly increasing every day" for inclusion in a report. Specifically, he wants the corrected stock prices H'_1, H'_2, \ldots, H'_N to satisfy H'_1 < H'_2 < \cdots < H'_N.

The correction is performed by individually changing the stock price of each day. When changing the stock price on day i from H_i to H'_i, the cost is |H_i - H'_i|. Takahashi wants to minimize the total cost of changes across all days, \sum_{i=1}^{N} |H_i - H'_i|.

However, the corrected stock price H'_i for each day must be an integer.

Find the minimum total cost when correcting the stock prices so that they are strictly monotonically increasing across all days.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq H_i \leq 10^9
• All inputs are integers.

Sample Input 1

5
5 3 2 4 5

Sample Output 1

6

Sample Input 2

7
3 3 3 3 3 3 3

Sample Output 2

12

Sample Input 3

10
10 1 12 3 14 5 16 7 18 9

Sample Output 3

50

Problem Statement

Takahashi has N stone tablets arranged in a circle. The tablets are numbered 1, 2, \dots, N in adjacent order, and the weight of tablet i is A_i. Tablet N and tablet 1 are also adjacent.

Takahashi repeats the following operation until only one tablet remains.

• Choose two tablets that are adjacent on the circle, and merge them into one. The cost of merging is equal to the sum of the weights of the two chosen tablets. The weight of the new tablet created by the merge is also equal to the sum of the weights of the two chosen tablets. The new tablet is placed at the position where the original two tablets were removed, and becomes adjacent to the tablets that were on the opposite sides of the original two tablets. In this way, the remaining tablets continue to maintain a circular structure.

Find the minimum possible total cost incurred across all operations.

Constraints

• 2 \leq N \leq 3000
• 1 \leq A_i \leq 10^9
• All inputs are integers

Sample Input 1

4
3 1 4 1

Sample Output 1

18

Sample Input 2

3
10 20 30

Sample Output 2

90

Sample Input 3

8
7 2 9 4 6 3 8 5

Sample Output 3

132

Sample Input 4

30
12 45 7 23 89 34 56 78 11 90 5 67 38 42 19 73 61 29 84 16 50 99 3 27 64 8 71 36 14 52

Sample Output 4

6201

Sample Input 5

2
1000000000 1000000000

Sample Output 5

2000000000