Problem Statement

Takahashi is conducting an experiment by rolling \(N\) dice on a line of squares.

The squares are arranged in a row, numbered \(1\) through \(M\). The square numbers are assigned sequentially from one end as \(1,2,\dots,M\).

Each die \(i\) (\(1 \leq i \leq N\)) is initially placed on square \(S_i\). Multiple dice may be placed on the same square, but the dice do not affect each other and are treated independently.

Each die is a standard six-sided die, with numbers \(1\) through \(6\) written on its six faces, one per face. The sum of the numbers on opposite faces is always \(7\).

In this problem, the orientation of a die is represented by a pair of the top face number and the front face number. The front face is the face facing in the direction of increasing square numbers.

In the initial state of die \(i\), the top face number is \(U_i\) and the front face number is \(F_i\). Since the top and front faces are neither the same face nor opposite faces, it is guaranteed that \(U_i \neq F_i\) and \(U_i+F_i \neq 7\).

Takahashi performs \(Q\) operations in order. In the \(j\)-th operation (\(1 \leq j \leq Q\)), he rolls die \(d_j\) by \(1\) square in direction \(c_j\) (+ or -).

When rolling a die, let \(u\) be the top face number and \(f\) be the front face number immediately before the roll. The position and orientation change according to the following rules:

• Rolling in the + direction (direction of increasing square numbers):
• The position increases by \(1\).
• The new top face number becomes \(7-f\), and the new front face number becomes \(u\).
• This corresponds to a rotation where the face that was the front becomes the bottom, the face that was the back becomes the top, and the face that was the top becomes the front.

• Rolling in the - direction (direction of decreasing square numbers):
• The position decreases by \(1\).
• The new top face number becomes \(f\), and the new front face number becomes \(7-u\).
• This corresponds to the reverse rotation of the + direction: the face that was the back becomes the bottom, the face that was the front becomes the top, and the face that was the top becomes the back.

It is guaranteed that throughout all operations, the position of each die remains within the range of \(1\) to \(M\), inclusive.

After completing all \(Q\) operations, find the final position and top face number for each die. You do not need to output the front face number.

Constraints

• \(1 \leq N \leq 2\times 10^5\)
• \(1 \leq M \leq 10^9\)
• \(1 \leq Q \leq 2\times 10^5\)
• \(N+Q \leq 2\times 10^5\)
• \(1 \leq S_i \leq M\) (\(1 \leq i \leq N\))
• \(1 \leq U_i \leq 6\) (\(1 \leq i \leq N\))
• \(1 \leq F_i \leq 6\) (\(1 \leq i \leq N\))
• \(U_i \neq F_i\) and \(U_i+F_i \neq 7\) (\(1 \leq i \leq N\))
• \(1 \leq d_j \leq N\) (\(1 \leq j \leq Q\))
• \(c_j\) is + or - (\(1 \leq j \leq Q\))
• As a result of operations, the position of any die will never be less than \(1\) or exceed \(M\).
• All input values except \(c_j\) are integers.

Sample Input 1

1 5 3
2 1 2
1 +
1 +
1 -

Sample Output 1

3 5

Sample Input 2

3 6 7
1 1 2
6 6 5
3 3 1
1 +
2 -
3 -
3 +
1 +
2 +
1 -

Sample Output 2

2 5
6 6
3 3

Sample Input 3

5 20 15
1 1 3
20 2 4
10 3 2
5 4 1
15 5 3
1 +
2 -
3 +
4 -
5 +
1 +
3 +
2 -
5 -
4 +
1 -
3 -
2 +
5 +
4 -

Sample Output 3

2 4
19 4
11 5
4 1
16 4

Sample Input 4

10 1000000000 36
1 1 2
1000000000 6 4
500000000 2 3
999999999 3 1
123456789 4 5
987654321 5 1
2 1 3
999999998 2 4
400000000 3 6
600000000 6 2
1 +
2 -
7 -
8 +
4 +
3 +
5 -
6 +
9 +
10 -
1 -
2 +
7 +
8 +
4 -
3 +
5 +
6 -
9 -
10 +
1 +
2 -
7 -
8 -
4 +
3 -
5 -
6 +
9 +
10 -
1 +
2 -
7 +
8 +
4 -
3 +

Sample Output 4

3 6
999999998 1
500000002 5
999999999 3
123456788 5
987654322 6
2 1
1000000000 5
400000001 1
599999999 2

Sample Input 5

1 2 15
1 1 2
1 +
1 -
1 +
1 -
1 +
1 -
1 +
1 -
1 +
1 -
1 +
1 -
1 +
1 -
1 +

Sample Output 5

2 5

Problem Statement

Takahashi is in charge of lighting at an event venue partitioned into a grid with H rows and W columns. Each cell has a brightness value, and the brightness of the cell at the i-th row from the top and j-th column from the left is G_{i,j}. Note that the brightness values can be negative.

Takahashi will choose exactly one cell in the venue to install a spotlight. If he installs a spotlight at cell (r, c), located at the r-th row from the top and c-th column from the left, all cells in the r-th row (including cell (r, c) itself) and all cells in the c-th column (including cell (r, c) itself) will be illuminated in a cross shape.

The total brightness of all illuminated cells is called the lighting score of that installation location. Although cell (r, c) belongs to both the r-th row and the c-th column, its brightness is counted only once in the calculation of the lighting score.

That is, the lighting score when a spotlight is installed at cell (r, c) is given by the following formula:

\sum_{j=1}^{W} G_{r,j} + \sum_{i=1}^{H} G_{i,c} - G_{r,c}

Takahashi wants to install the spotlight at a cell that maximizes the lighting score.

Find the maximum possible lighting score.

Constraints

• 1 \leq H \leq 2000
• 1 \leq W \leq 2000
• -10^9 \leq G_{i,j} \leq 10^9
• All input values are integers.

Sample Input 1

3 3
1 2 3
4 5 6
7 8 9

Sample Output 1

33

Sample Input 2

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

Sample Output 2

-10

Sample Input 3

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

Sample Output 3

30

Sample Input 4

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

Sample Output 4

56

Sample Input 5

1 1
-1000000000

Sample Output 5

-1000000000

Problem Statement

Takahashi is the head of the school's gardening committee. The school has N flower beds, each numbered from 1 to N.

Each flower bed i (1 \leq i \leq N) has an initial moisture level L_i. If a flower bed's moisture level is at least K, the flowers grow healthily, but if it falls below K, the flowers wilt. To keep the flowers healthy, Takahashi will perform M watering operations.

In the j-th watering operation (1 \leq j \leq M), he increases the moisture level by Z_j for all consecutively numbered flower beds from flower bed X_j to flower bed Y_j (X_j \leq Y_j). The moisture levels do not change due to any factors other than watering.

After all watering operations are completed, the final moisture level of each flower bed is the initial moisture level plus the total increase from all watering operations. Find the number of flower beds whose final moisture level is at least K, that is, the number of flower beds that Takahashi was able to keep healthy.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 0 \leq K \leq 10^9
• 0 \leq L_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq X_j \leq Y_j \leq N (1 \leq j \leq M)
• 1 \leq Z_j \leq 10^4 (1 \leq j \leq M)
• All input values are integers

Sample Input 1

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

Sample Output 1

3

Sample Input 2

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

Sample Output 2

6

Sample Input 3

10 6 100
50 80 30 90 45 70 25 60 85 40
1 5 20
3 8 30
2 6 15
6 10 25
1 3 10
8 10 20

Sample Output 3

7

Problem Statement

Takahashi has received N encrypted messages. Each encrypted message is a string of length M consisting of lowercase English letters, but due to noise during transmission, some positions have become unreadable, and even the readable positions may contain errors.

Meanwhile, N original plaintext strings of length M are given, which are supposed to be the sources of these encrypted messages. It is believed that during encryption, all plaintexts were cyclically shifted by a common shift amount to produce the encrypted messages, but neither the exact shift amount nor the correspondence between encrypted messages and plaintexts is known.

Takahashi wants to find the shift amount and correspondence that minimize the total number of mismatches.

Definitions

Each position in a string is represented by an integer from 1 to M.

Cyclic shift and position correspondence: Comparing an encrypted message with a plaintext using shift amount r (an integer with 0 \leq r < M) means comparing the encrypted message with the string obtained by cyclically shifting the plaintext r characters to the left, at corresponding positions. Specifically, the plaintext position corresponding to position p in the encrypted message is ((p + r - 1) \bmod M) + 1.

Noise information: Each encrypted message i (1 \leq i \leq N) is paired with a received string S_i and a readability string C_i. If position p of C_i is 0, then the character at that position is readable and is subject to comparison. If it is 1, it means that position was unreadable and is excluded from comparison.

Number of mismatches: The number of mismatches when pairing encrypted message i with plaintext j using shift amount r is defined as follows. For all positions p (1 \leq p \leq M) where position p of C_i is 0, compare the character at position p of S_i with the character at position ((p + r - 1) \bmod M) + 1 of T_j. The number of positions where they differ is the number of mismatches.

Objective

Choose one shift amount r (0 \leq r < M), and determine a one-to-one correspondence between the N encrypted messages and the N plaintexts (i.e., assign one plaintext to each of encrypted messages 1, 2, \ldots, N without repetition). The shift amount r is common to all correspondence pairs.

Consider the total number of mismatches across all correspondence pairs, and find its minimum value.

Update Queries

Q updates are applied sequentially to the encrypted messages or plaintexts. After each update, find the above minimum value for the current state.

Constraints

• 1 \leq N \leq 5
• 1 \leq M \leq 500
• 1 \leq Q \leq 500
• M Q \leq 5 \times 10^4
• S_i is a string of length M consisting of lowercase English letters (1 \leq i \leq N)
• C_i is a string of length M consisting of 0 and 1 (1 \leq i \leq N)
• T_j is a string of length M consisting of lowercase English letters (1 \leq j \leq N)
• Each update query is one of the following three types:
• Format 1 i p x: 1 \leq i \leq N, 1 \leq p \leq M, x is a lowercase English letter
• Format 2 i p b: 1 \leq i \leq N, 1 \leq p \leq M, b is 0 or 1
• Format 3 j p x: 1 \leq j \leq N, 1 \leq p \leq M, x is a lowercase English letter

Sample Input 1

2 4 5
abca
0000
zzzz
1010
bcaa
zzzz
1 1 2 c
2 2 1 0
3 1 4 b
2 1 3 1
1 2 4 a

Sample Output 1

1
1
2
2
3

Sample Input 2

1 5 4
abcde
00101
cdeab
3 1 1 a
2 1 3 0
1 1 5 b
3 1 4 z

Sample Output 2

0
1
1
2

Sample Input 3

3 8 10
abcdefgh
00001111
hgfedcba
01010101
aaaabbbb
11110000
cdefghab
fedcbahg
bbbbaaaa
1 1 4 z
2 3 2 0
3 2 8 a
1 2 1 f
2 1 5 0
3 1 3 x
2 2 4 0
1 3 8 c
3 3 5 z
2 1 1 1

Sample Output 3

3
3
3
4
4
5
5
5
5
5

Sample Input 4

5 20 15
abcdefghijklmnopqrst
00000000000000000000
zyxwvutsrqponmlkjihg
01010101010101010101
aaaaaaaaaabbbbbbbbbb
11111000001111100000
qwertyuiopasdfghjklz
00110011001100110011
mnopqrstuvwxyzabcdef
10000000000000000001
defghijklmnopqrstabc
ghijklmnopqrstuvwxyz
bbbbbbbbbbaaaaaaaaaa
poiuytrewqlkjhgfdsaz
nopqrstuvwxyzabcdefg
1 1 20 a
2 2 2 0
3 3 10 c
1 4 5 z
2 5 1 0
3 1 1 q
1 3 11 a
2 4 19 1
3 5 20 y
1 2 7 b
2 1 10 1
3 4 4 a
1 5 14 m
2 3 6 1
3 2 15 d

Sample Output 4

41
42
42
42
42
42
42
42
42
42
41
41
42
42
43

Sample Input 5

1 1 5
a
0
b
3 1 1 a
1 1 1 z
2 1 1 1
3 1 1 z
2 1 1 0

Sample Output 5

0
1
0
0
0

Problem Statement

Takahashi is opening a stall at a flea market and plans to sell M items. The items are numbered 1 through M, and the cost price of item j is C_j yen. Unsold items can be returned to the supplier, so no loss is incurred from unsold items.

There are N visitors to the flea market, numbered 1 through N. Visitor i is willing to pay up to V_{i,j} yen for item j (this is called visitor i's valuation of item j).

Takahashi knows each visitor's valuation in advance and sells each item at a price equal to the valuation. That is, if item j is sold to visitor i, the selling price is V_{i,j} yen, and the profit obtained from this transaction is V_{i,j} - C_j yen.

Takahashi decides the buyers of the items so that all of the following conditions are met:

• Since there is only 1 of each item, a single item cannot be sold to 2 or more visitors. That is, for each item, he either chooses at most one buyer or sells it to no one.
• Each visitor purchases at most 1 item. That is, for each visitor, they either choose at most one item to purchase or purchase nothing.
• No transaction with a negative profit is made. That is, to sell item j to visitor i, it must hold that V_{i,j} \geq C_j.

Under these conditions, find the maximum possible total profit Takahashi can obtain. Note that it is possible to choose not to sell any items, in which case the total profit is 0.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 14
• N \times M \leq 2 \times 10^5
• 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
• 0 \leq V_{i,j} \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
• All input values are integers.

Sample Input 1

3 2
5 4
8 3
6 10
4 7

Sample Output 1

9

Sample Input 2

2 3
100 200 300
50 150 250
99 199 299

Sample Output 2

0

Sample Input 3

8 5
10 20 15 8 30
12 18 20 7 35
9 25 14 10 29
30 10 18 8 31
11 22 16 20 10
5 19 40 9 32
13 21 15 8 30
50 5 5 5 5
10 20 15 100 60

Sample Output 3

167

Sample Input 4

20 12
40 25 60 10 75 55 30 90 15 50 65 20
100 20 70 9 80 54 33 95 15 55 70 22
39 40 61 12 74 100 31 20 18 49 66 25
45 30 59 30 76 56 80 91 10 52 64 19
10 25 100 11 75 54 29 120 16 50 63 21
41 26 60 10 200 55 30 90 15 50 65 20
80 24 58 9 74 53 32 89 14 120 64 18
42 100 62 13 73 57 28 88 17 51 90 30
40 25 60 10 75 55 30 90 15 50 65 20
0 0 0 0 0 0 0 0 0 0 0 0
60 45 80 25 90 70 50 110 35 75 85 40
38 27 65 8 78 52 35 93 20 48 67 22
90 10 10 10 10 10 10 10 10 10 10 10
20 60 20 60 20 60 20 60 20 60 20 60
55 35 75 15 85 65 45 105 25 70 80 30
43 28 63 14 77 58 34 92 19 53 68 24
70 70 70 70 70 70 70 70 70 70 70 70
41 24 59 11 76 56 29 91 16 51 66 23
120 130 140 150 160 170 180 190 200 210 220 230
5 200 5 200 5 200 5 200 5 200 5 200
44 29 64 13 79 59 36 94 21 54 69 26

Sample Output 4

955

Sample Input 5

1 1
1000000000
1000000000

Sample Output 5

0