Problem Statement

Takahashi manages N libraries in the city. Library i (1 \leq i \leq N) has M_i genres, and each genre is numbered from 1 to M_i.

The initial number of books in genre j (1 \leq j \leq M_i) of library i is S_{i,j}. It is possible for a genre to have an initial book count of 0.

One day, Aoki organized the lending records and found that there are Q unprocessed lending requests recorded in order. Takahashi will process these requests sequentially from the 1-st to the Q-th. The initial book counts represent the number of books at the time before processing these lending requests.

The k-th lending request (1 \leq k \leq Q) is "borrow 1 book of genre d_k from library v_k." Each lending request is processed as follows:

• If the current number of books of genre d_k in library v_k is 1 or more, the lending succeeds, and the number of books of that genre decreases by 1.
• If the current number of books of genre d_k in library v_k is 0, the lending fails, and the number of books does not change.

After processing all lending requests from the 1-st to the Q-th in order, output the remaining number of books for each genre in each library, and the number of requests that failed.

Constraints

• 1 \leq N \leq 1000
• 1 \leq M_i \leq 1000
• \sum_{i=1}^{N} M_i \leq 10^5
• 0 \leq S_{i,j} \leq 10^9
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq v_k \leq N
• 1 \leq d_k \leq M_{v_k}
• All input values are integers.

Sample Input 1

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

Sample Output 1

2 0
0
2

Sample Input 2

3
3 5 0 2
2 1 1
2 3 0
8
1 2
1 1
2 1
2 2
3 2
1 3
1 3
3 1

Sample Output 2

4 0 0
0 0
2 0
2

Sample Input 3

4
3 1000000000 0 5
4 2 3 1 0
1 100
2 10 20
12
1 1
1 2
1 2
1 3
2 4
2 4
3 1
3 1
4 1
4 2
4 2
2 3

Sample Output 3

999999999 0 4
2 3 0 0
98
9 18
4

Problem Statement

Takahashi has been assigned as the receptionist for a large party.

Invited guests arrive at the party one after another. Each guest is assigned a guest number, which is an integer between 1 and 10^9 inclusive, and different guests are assigned different numbers. Takahashi records each arriving person on the guest list. He may also receive inquiries from the venue staff asking, "Has this person already arrived?"

The guest list is initially empty.

Takahashi performs Q operations in order. The i-th operation is represented by a pair of type T_i and guest number X_i, and is one of the following two types:

• T_i = 1 (Record arrival): Add the person with guest number X_i to the guest list. It is guaranteed that X_i is not already in the guest list at the time this operation is performed.
• T_i = 2 (Arrival inquiry): Check whether the person with guest number X_i is currently in the guest list.

For each operation where T_i = 2, determine whether the person with the specified guest number is in the guest list.

Constraints

• 1 \leq Q \leq 4 \times 10^5
• T_i \in \{1, 2\}
• 1 \leq X_i \leq 10^9
• For operations where T_i = 1, X_i is not already in the guest list at that time
• There is at least one operation where T_i = 2
• All input values are integers

Sample Input 1

5
1 10
2 10
2 3
1 3
2 3

Sample Output 1

Yes
No
Yes

Sample Input 2

7
2 100
1 50
2 50
1 100
2 100
2 75
2 50

Sample Output 2

No
Yes
Yes
No
Yes

Sample Input 3

12
1 8
1 100
2 8
2 9
1 999999937
2 999999937
1 42
2 100
2 42
2 1000000000
1 1000000000
2 1000000000

Sample Output 3

Yes
No
Yes
Yes
Yes
No
Yes

Sample Input 4

24
2 500
1 500
1 123456789
2 1
2 500
1 1
2 1
1 999999999
2 123456789
2 999999998
1 777777777
1 250000000
2 777777777
2 250000000
2 100
1 100
2 100
1 314159265
2 314159265
2 271828182
1 271828182
2 271828182
2 999999999
2 123456

Sample Output 4

No
No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No

Sample Input 5

1
2 1000000000

Sample Output 5

No

Problem Statement

Takahashi has a log consisting of N parts connected in a row. The parts are numbered 1, 2, \ldots, N from left to right, and the length of part i is A_i.

There are boundaries between adjacent parts, and there are N - 1 such boundaries. Namely, the boundary between part i and part i + 1 (1 \leq i \leq N - 1). Takahashi chooses K of these boundaries to cut, dividing the log into K + 1 fragments.

The length of each fragment is determined by the sum of the lengths of the parts contained in that fragment. Let M be the maximum length among the K + 1 fragments.

Find the minimum possible value of M when the cut positions are chosen optimally.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N - 1
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

5 2
3 5 4 7 6

Sample Output 1

11

Sample Input 2

4 1
1 2 3 4

Sample Output 2

6

Sample Input 3

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

Sample Output 3

19

Sample Input 4

20 5
14 7 23 11 5 19 8 30 12 6 17 25 3 9 21 16 28 4 13 10

Sample Output 4

55

Sample Input 5

2 1
1000000000 1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi is in charge of managing the meeting rooms at his office. Today, N meetings are scheduled, and all meetings must be assigned to some meeting room.

The N meetings are numbered from 1 to N. Meeting i (1 \leq i \leq N) starts at time S_i and ends at time E_i. Each meeting occupies a meeting room during the half-open interval [S_i, E_i).

For two meetings i, j to be assigned to the same meeting room, the intervals [S_i, E_i) and [S_j, E_j) must not overlap. In particular, if the end time of one meeting coincides with the start time of another meeting, they can be held consecutively in the same meeting room.

The office has a sufficient number of meeting rooms available, but Takahashi wants to accommodate all N meetings using as few meeting rooms as possible.

Assign each meeting to exactly one meeting room such that no meeting room contains meetings with overlapping time intervals. Find the minimum number of meeting rooms required.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq S_i < E_i \leq 10^9
• All input values are integers.
• There may be multiple meetings with the same pair of start time and end time.

Sample Input 1

3
1 4
2 6
4 7

Sample Output 1

2

Sample Input 2

4
1 5
2 6
3 7
4 8

Sample Output 2

4

Sample Input 3

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

Sample Output 3

4

Sample Input 4

15
6 14
7 11
8 12
9 13
10 15
0 3
1 4
3 7
14 20
15 18
16 22
20 25
11 16
4 6
18 24

Sample Output 4

5

Sample Input 5

1
0 1000000000

Sample Output 5

1

Problem Statement

Takahashi has a grid with H rows and W columns. The cell at the i-th row from the top (1 \leq i \leq H) and the j-th column from the left (1 \leq j \leq W) is denoted as (i, j). The value of cell (i, j) is the integer A_{i,j}.

Takahashi freely chooses a set of rows R \subseteq \{1, 2, \ldots, H\} and a set of columns C \subseteq \{1, 2, \ldots, W\}. Each of R and C may be the empty set.

A cell (i, j) is painted if at least one of i \in R or j \in C holds. Let S be the sum of the values of the painted cells. That is,

S = \sum_{\substack{(i,j) \\ i \in R \text{ or } j \in C}} A_{i,j}

If no cells are painted (i.e., R = C = \emptyset), then S = 0.

Find the maximum value of S over all possible choices of R and C.

> Note (equivalent expression using inclusion-exclusion principle): The above S can also be computed as follows.

>

> S = \sum_{i \in R} \sum_{j=1}^{W} A_{i,j} + \sum_{j \in C} \sum_{i=1}^{H} A_{i,j} - \sum_{i \in R} \sum_{j \in C} A_{i,j}

Constraints

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

Sample Input 1

2 3
5 -2 4
-3 6 -1

Sample Output 1

13

Sample Input 2

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

Sample Output 2

0

Sample Input 3

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

Sample Output 3

50

Sample Input 4

8 8
1000000000 -1000000000 5 -7 8 -9 10 -11
-1000000000 1000000000 -6 7 -8 9 -10 12
13 -14 1000000000 -1000000000 15 -16 17 -18
-19 20 -1000000000 1000000000 -21 22 -23 24
25 -26 27 -28 1000000000 -1000000000 29 -30
-31 32 -33 34 -1000000000 1000000000 -35 36
37 -38 39 -40 41 -42 1000000000 -1000000000
-43 44 -45 46 -47 48 -1000000000 1000000000

Sample Output 4

4000000321

Sample Input 5

1 1
1000000000

Sample Output 5

1000000000