Problem Statement

Takahashi runs a store. This store sells N types of products, each distinguished by a number from 1 to N. The regular price of product i is A_i yen per item.

This store has a membership system, where member customers receive a discount of K yen per item. Specifically, when a non-member customer purchases product i, the price per item is the regular price of A_i yen. When a member customer purchases product i, the price per item is \max(A_i - K, 0) yen, which is the regular price minus K yen (the discount does not exceed the regular price, and the price does not go below 0 yen).

Now, M purchase records are given. The j-th record contains a value S_j indicating whether the customer is a member (1 for member, 0 for non-member), the product number P_j purchased, and the quantity D_j purchased.

The purchase amount for each record is the price per item multiplied by the quantity D_j. Find the total purchase amount across all purchase records.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^5
• 0 \leq K \leq 10^5
• 1 \leq A_i \leq 10^5 (1 \leq i \leq N)
• S_j \in \{0, 1\} (1 \leq j \leq M)
• 1 \leq P_j \leq N (1 \leq j \leq M)
• 1 \leq D_j \leq 10^5 (1 \leq j \leq M)
• All inputs are integers.
• It is guaranteed that the answer is at most 10^{15}.

Sample Input 1

3 4 20
100 50 10
0 1 2
1 2 3
1 3 5
0 2 1

Sample Output 1

340

Sample Input 2

2 3 0
30 70
1 1 4
0 2 1
1 2 2

Sample Output 2

330

Sample Input 3

6 8 15
40 120 15 200 80 5
1 1 10
0 2 3
1 3 7
0 4 1
1 5 4
0 6 20
1 4 2
0 1 5

Sample Output 3

1740

Sample Input 4

15 20 35
20 55 90 35 120 10 200 75 60 150 5 300 45 95 130
1 1 8
0 2 6
1 3 5
0 4 10
1 5 2
0 6 30
1 7 1
0 8 7
1 9 9
0 10 3
1 11 12
0 12 1
1 4 4
0 3 2
1 8 6
0 13 5
1 14 3
0 15 2
1 2 11
0 7 4

Sample Output 4

5195

Sample Input 5

1 1 100000
1
1 1 100000

Sample Output 5

0

Problem Statement

Takahashi has a device with N lamps arranged in a row. Each lamp is either on (1) or off (0).

Denoting the lamps from left to right as b_1, b_2, \ldots, b_N, the state of the device is represented by the integer

X = \sum_{i=1}^{N} b_i \cdot 2^{i-1}

That is, the i-th lamp from the left, b_i, corresponds to the i-th bit from the bottom in the binary representation of X (the leftmost lamp is the least significant bit).

The following operation is repeatedly performed on Takahashi's device. The operation is performed at most K times, but may stop midway.

One operation: Check the leftmost lamp of the current sequence.

- If it is on (1), do nothing and terminate all operations.

- If it is off (0), remove that lamp from the sequence and append one on (1) lamp to the right end (the length of the sequence remains N). If the number of operations has not yet reached K, perform the operation again.

In other words, "as long as the leftmost lamp is off, remove it and append an on lamp to the right end" is performed up to K times. The process terminates when the leftmost lamp is confirmed to be on, or when K operations have been performed.

After this process, Aoki brings M lamp sequences. Each lamp sequence also has length N, and the state of the j-th lamp sequence is represented by the integer Y_j, using the same bit correspondence as Takahashi's device.

Takahashi chooses a single common split position p (1 \le p \le N - 1) for all M + 1 lamp sequences — his own processed lamp sequence and Aoki's M lamp sequences. Each lamp sequence is divided into the left p lamps and the right N - p lamps.

For each lamp sequence, letting the lamps of the left part from left to right be c_1, c_2, \ldots, c_p, its integer value is defined as

\sum_{i=1}^{p} c_i \cdot 2^{i-1}

Let A be the sum of the integer values of the left parts of all M+1 lamp sequences.

Similarly, for each lamp sequence, letting the lamps of the right part from left to right be d_1, d_2, \ldots, d_{N-p}, its integer value is defined as

\sum_{i=1}^{N-p} d_i \cdot 2^{i-1}

(Note that the powers of 2 restart from 2^0 within the right part.) Let B be the sum of the integer values of the right parts of all M+1 lamp sequences.

Takahashi chooses the split position p to maximize A + B. Find the maximum value of A + B.

Constraints

• 2 \leq N \leq 46
• 0 \leq K \leq 10^9
• 0 \leq M \leq 2 \times 10^5
• 0 \leq X < 2^N
• 0 \leq Y_j < 2^N (1 \leq j \leq M)
• All inputs are integers
• Under these constraints, the answer fits in a signed 64-bit integer

Sample Input 1

5 2 2 4
3 16

Sample Output 1

23

Sample Input 2

4 0 1 9
6

Sample Output 2

8

Sample Input 3

12 7 6 1384
0 4095 2730 1365 2048 1234

Sample Output 3

7616

Sample Input 4

46 1000000000 10 35184372088832
0 1 70368744177663 70368744177662 35184372088831 35184372088832 1234567890123 45678901234567 60000000000000 42

Sample Output 4

194194222917695

Sample Input 5

2 1000000000 0 0

Sample Output 5

2

Problem Statement

Takahashi is performing train rearrangement work.

Initially, the train consists of A red (R) cars from the front, followed by B blue (B) cars connected behind them. In other words, representing the initial state as a string, it is a string of length N = A + B where A characters R are followed by B characters B.

Takahashi can perform the following operation zero or more times:

• Choose an integer k (1 \leq k \leq N - 1). Detach the last k cars from the current train. That is, split the train into the front N - k cars and the rear k cars.
• Insert the detached rear k cars as a single block, maintaining their order, into any position within the front N - k cars and reconnect them. The possible insertion positions are: before the front, after the end, or between any two adjacent cars, for a total of N - k + 1 possible positions.

Each operation is performed on the current state of the train at that point.

You are given a string T of length N representing the target arrangement of cars. Find the minimum number of operations needed to transform the initial state into the arrangement T.

However, if the number of R characters in T is not A (i.e., the composition of cars differs from the initial state), it is impossible to achieve the target arrangement. In that case, output -1.

Constraints

• 1 \leq A
• 1 \leq B
• A + B \leq 10^7
• T is a string of length A + B consisting only of R and B
• The number of R characters in T is not necessarily A

Sample Input 1

2 2
RBBR

Sample Output 1

1

Sample Input 2

3 2
RRBBB

Sample Output 2

-1

Sample Input 3

7 6
RBRBBRRBRRBBR

Sample Output 3

4

Sample Input 4

25 20
BBBBBBBBBBBBBBBBBBBBRRRRRRRRRRRRRRRRRRRRRRRRR

Sample Output 4

1

Sample Input 5

1 1
RB

Sample Output 5

0

Problem Statement

There is a corridor consisting of L rooms arranged in a horizontal row. The rooms are numbered from 0 to L - 1 from left to right.

There is a door between each pair of adjacent rooms. Specifically, for each integer x satisfying 1 \leq x \leq L - 1, there is door x between room x - 1 and room x. Both ends of the corridor (the left side of room 0 and the right side of room L-1) are outer walls and cannot be passed through.

This corridor has N types of security patterns configured. Security pattern i has modulus A_i, initial value R_i, and time coefficient V_i. At integer time t, if door x (1 \leq x \leq L - 1) satisfies

x \equiv R_i + V_i \cdot t \pmod{A_i}

then security pattern i places 1 lock on that door. Multiple security patterns may place locks on the same door at the same time.

The weight of door x at time t is defined as the total number of locks placed on that door at time t.

You are given Q queries. In query j, Takahashi is in room S_j at time T_j. Fix the state of the locks at time T_j (without considering changes over time) and consider the following.

Takahashi's stamina is P_j. For Takahashi to reach room c from room S_j, he must pass through all doors between S_j and c in order. If the total weight of the doors he passes through is at most P_j, then Takahashi can reach room c.

For each query, find the number of rooms Takahashi can reach. Note that room S_j where Takahashi starts is also counted as a reachable room.

Constraints

• 1 \leq N \leq 10^5
• 2 \leq L \leq 10^9
• 1 \leq Q \leq 10^5
• N \times Q \leq 3 \times 10^5
• 1 \leq A_i \leq 10^9
• 0 \leq R_i \leq A_i - 1
• 0 \leq V_i \leq A_i - 1
• 0 \leq T_j \leq 10^9
• 0 \leq S_j \leq L - 1
• 0 \leq P_j \leq 10^{14}
• All inputs are integers.

Sample Input 1

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

Sample Output 1

1
6
4
6

Sample Input 2

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

Sample Output 2

7
2
5
1
8

Sample Input 3

8 50 10
7 0 3
11 5 2
13 12 0
6 4 5
17 8 9
10 1 7
9 3 3
25 24 1
0 0 5
1 10 12
2 20 0
5 25 30
10 49 100
12345 17 50
999999 33 7
42 4 20
7 48 1
100 12 1000

Sample Output 3

8
27
5
50
50
50
19
30
8
50

Sample Input 4

20 100000 15
1000 0 1
99991 12345 67890
2 1 1
3 2 0
97 96 13
1000000000 999999999 0
50000 25000 24999
65536 32768 12345
12345 6789 1111
88888 77777 66666
100 0 99
999 998 997
100000 54321 1234
271828 1828 271
314159 26535 89793
42 17 23
73 0 72
1000000000 0 999999999
1234567 765432 123456
987654321 123456789 98765432
0 0 0
1 99999 10
2 50000 1000
1000 12345 50000
999999999 54321 100000000000000
314159265 999 123456789
271828182 88888 9876543210
42 4242 42
73 7300 7300
1000000000 1 1
555555555 77777 333333
123456789 23456 1000000
987654321 65432 999999999999
80808080 90909 12345678901234
60606060 10101 0

Sample Output 4

1
11
2238
68321
100000
100000
100000
96
15474
2
100000
100000
100000
100000
2

Sample Input 5

1 2 5
1 0 0
0 0 0
0 0 1
1000000000 1 0
1000000000 1 100000000000000
123 0 100000000000000

Sample Output 5

1
2
1
2
2

Problem Statement

Takahashi is a data analyst working in the human resources department of a company. The company has N employees, each assigned an employee number from 1 to N.

In this company, there exist boss-subordinate relationships among employees. Each employee i (2 \leq i \leq N) has exactly one direct boss P_i, and it is guaranteed that P_i < i. Employee 1 is the president and has no direct boss. This relationship forms a rooted tree with employee 1 as the root.

Employee u is a subordinate of employee v if u is a descendant of v in the rooted tree. In other words, v is not on the path from v to the root that includes u, but v is on the path from u to the root. More precisely, u is a subordinate of v if and only if employee v can be reached from employee u by following the direct boss relationship one or more times. Note that employee v itself is not considered a subordinate of employee v.

Each employee i has a positive integer value A_i representing their salary.

For organizational analysis, Takahashi needs to process a total of Q queries of the following two types. Each query is processed sequentially in the given order, and changes made by update queries are reflected in all subsequent queries.

Query 1 (Update): 1 v x — Change the salary of employee v to x.

Query 2 (Investigation): 2 v — Among all subordinates of employee v, find and output the number of those whose salary is strictly greater than the salary of employee v at the time the query is processed.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq P_i < i (2 \leq i \leq N)
• For Query 1, 1 \leq v \leq N and 1 \leq x \leq 10^9
• For Query 2, 1 \leq v \leq N
• There is at least one Query 2
• All input values are integers

Sample Input 1

5 5
10 5 15 8 3
1 1 2 2
2 1
2 2
1 5 20
2 2
2 1

Sample Output 1

1
1
2
2

Sample Input 2

4 4
5 10 3 7
1 2 2
2 3
2 4
1 3 100
2 2

Sample Output 2

0
0
1

Sample Input 3

10 8
50 30 70 20 60 10 80 40 90 55
1 1 2 2 3 3 4 4 5
2 1
2 2
2 3
1 4 100
2 2
1 1 85
2 1
2 5

Sample Output 3

5
4
1
5
2
0

Sample Input 4

20 15
100 90 80 70 60 50 40 30 20 10 110 120 130 140 150 55 65 75 85 95
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
2 1
2 2
2 3
1 1 200
2 1
1 11 500
2 5
1 5 1
2 5
2 4
1 10 999
2 9
2 1
1 3 1000
2 3

Sample Output 4

5
2
4
0
2
3
2
2
2
0

Sample Input 5

1 3
42

1 1 100
2 1
1 1 1

Sample Output 5

0