Problem Statement

There are N items. You are given strings T and A of length N that represent which items Takahashi and Aoki want, respectively. Let T_i and A_i be the i-th (1\leq i\leq N) characters of T and A, respectively.

Takahashi wants the i-th item when T_i is o, and does not want the i-th item when T_i is x. Similarly, Aoki wants the i-th item when A_i is o, and does not want the i-th item when A_i is x.

Determine whether there exists an item that both of them want.

Constraints

• 1\leq N\leq 100
• N is an integer.
• T and A are strings of length N consisting of o and x.

Sample Input 1

4
oxoo
xoox

Sample Output 1

Yes

The third item is wanted by both of them, so output Yes.

Sample Input 2

5
xxxxx
ooooo

Sample Output 2

No

There is no item that both of them want, so output No.

Sample Input 3

10
xoooxoxxxo
ooxooooxoo

Sample Output 3

Yes

Problem Statement

There are N people numbered 1 through N. Each person has a integer score called programming ability; person i's programming ability is P_i points. How many more points does person 1 need, so that person 1 becomes the strongest? In other words, what is the minimum non-negative integer x such that P_1 + x > P_i for all i \neq 1?

Constraints

• 1\leq N \leq 100
• 1\leq P_i \leq 100
• All input values are integers.

Sample Input 1

4
5 15 2 10

Sample Output 1

11

Person 1 becomes the strongest when their programming skill is 16 points or more, so the answer is 16-5=11.

Sample Input 2

4
15 5 2 10

Sample Output 2

0

Person 1 is already the strongest, so no more programming skill is needed.

Sample Input 3

3
100 100 100

Sample Output 3

1

Problem Statement

Find the N integer sequences A_0,\ldots,A_{N-1} defined as follows.

• For each i (0\leq i \leq N-1), the length of A_i is i+1.
• For each i and j (0\leq i \leq N-1, 0 \leq j \leq i), the (j+1)-th term of A_i, denoted by a_{i,j}, is defined as follows.
  • a_{i,j}=1, if j=0 or j=i.
  • a_{i,j} = a_{i-1,j-1} + a_{i-1,j}, otherwise.

Constraints

• 1 \leq N \leq 30
• N is an integer.

Sample Input 1

3

Sample Output 1

1
1 1
1 2 1

Sample Input 2

10

Sample Output 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Problem Statement

Takahashi has an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.
It is guaranteed that A is non-decreasing.

Takahashi performs M operations on this integer sequence. In the i-th operation (1\leq i\leq M), he performs the following operation:

If the sequence A contains B_i as an element, select one such element and delete it. If no such element exists, do nothing.

Note that since A is non-decreasing, the sequence after the operation is uniquely determined regardless of the choice of element, and remains non-decreasing.

Find A after performing M operations.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 1 \leq A_i,B_i \leq 10^9
• The integer sequence A is non-decreasing.
• All input values are integers.

Sample Input 1

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

Sample Output 1

1 3 3 5 6

Initially, A is A=(1,2,2,3,3,3,5,6).
The operations are performed as follows:

• Delete one 2 from A, and A becomes A=(1,2,3,3,3,5,6) after the operation.
• Delete one 2 from A, and A becomes A=(1,3,3,3,5,6) after the operation.
• Since A does not contain 7 as an element, do nothing. A remains A=(1,3,3,3,5,6) after the operation.
• Delete one 3 from A, and A becomes A=(1,3,3,5,6) after the operation.
• Since A does not contain 2 as an element, do nothing. A remains A=(1,3,3,5,6) after the operation.

Therefore, after all operations, A=(1,3,3,5,6), so output the elements in this order separated by spaces.

Sample Input 2

1 2
1
1 1

Sample Output 2

A becomes empty after the operations, so output nothing.

Problem Statement

You are given a string S of length N. You are also given Q queries, which you should process in order.

The i-th query is as follows:

• Given an integer X_i and a character C_i, replace the X_i-th character of S with C_i. Then, print the number of times the string ABC appears as a substring in S.

Here, a substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, ab is a substring of abc, but ac is not a substring of abc.

Constraints

• 3 \le N \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• S is a string of length N consisting of uppercase English letters.
• 1 \le X_i \le N
• C_i is an uppercase English letter.

Sample Input 1

7 4
ABCDABC
4 B
3 A
5 C
4 G

Sample Output 1

2
1
1
0

After processing each query, S becomes as follows.

• After the first query: S= ABCBABC. In this string, ABC appears twice as a substring.
• After the second query: S= ABABABC. In this string, ABC appears once as a substring.
• After the third query: S= ABABCBC. In this string, ABC appears once as a substring.
• After the fourth query: S= ABAGCBC. In this string, ABC appears zero times as a substring.

Sample Input 2

3 3
ABC
1 A
2 B
3 C

Sample Output 2

1
1
1

There are cases where S does not change through processing a query.

Sample Input 3

15 10
BBCCBCACCBACACA
9 C
11 B
5 B
11 B
4 A
8 C
8 B
5 B
7 B
14 B

Sample Output 3

0
0
0
0
1
1
2
2
1
1

Problem Statement

A bus is in operation. The number of passengers on the bus is always a non-negative integer.

At some point in time, the bus had zero or more passengers, and it has stopped N times since then. At the i-th stop, the number of passengers increased by A_i. Here, A_i can be negative, meaning the number of passengers decreased by -A_i. Also, no passengers got on or off the bus other than at the stops.

Find the minimum possible current number of passengers on the bus that is consistent with the given information.

Constraints

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

Sample Input 1

4
3 -5 7 -4

Sample Output 1

3

If the initial number of passengers was 2, the current number of passengers would be 2 + 3 + (-5) + 7 + (-4) = 3, and the number of passengers on the bus would have always been a non-negative integer.

Sample Input 2

5
0 0 0 0 0

Sample Output 2

0

Sample Input 3

4
-1 1000000000 1000000000 1000000000

Sample Output 3

3000000000

Problem Statement

There is an H \times W grid, and each cell contains an integer 0 or 1.
The information of the integer written in each cell is given as H strings S_1, S_2, \dots, S_H of length W. If the j-th character of S_i is 0, then 0 is written in the cell at the i-th row from the top and the j-th column from the left of the grid; if the j-th character of S_i is 1, then 1 is written in that cell.

Find the number of rectangular regions where the sum of the written integers equals K.
More formally, find the number of quadruples of integers (r_1, c_1, r_2, c_2) satisfying all of the following conditions:

• 1 \le r_1 \le r_2 \le H
• 1 \le c_1 \le c_2 \le W
• The sum of the integers written in the cell at the i-th row from the top and the j-th column from the left, over all pairs of integers (i, j) satisfying r_1 \le i \le r_2, c_1 \le j \le c_2, equals K.

Constraints

• H and W are integers between 1 and 500, inclusive.
• K is an integer between 0 and HW, inclusive.
• S_i is a string of length W consisting of 0 and 1.

Sample Input 1

3 4 3
1001
1101
0110

Sample Output 1

8

There are eight rectangular regions where the sum of the written integers equals K:

• The rectangular region extracted from row 1 to row 2 from the top and column 1 to column 2 from the left
• The rectangular region extracted from row 1 to row 2 from the top and column 1 to column 3 from the left
• The rectangular region extracted from row 1 to row 2 from the top and column 2 to column 4 from the left
• The rectangular region extracted from row 1 to row 3 from the top and column 2 to column 3 from the left
• The rectangular region extracted from row 1 to row 3 from the top and column 3 to column 4 from the left
• The rectangular region extracted from row 2 to row 2 from the top and column 1 to column 4 from the left
• The rectangular region extracted from row 2 to row 3 from the top and column 1 to column 2 from the left
• The rectangular region extracted from row 2 to row 3 from the top and column 2 to column 3 from the left

Sample Input 2

5 4 20
0101
1010
0101
1010
0101

Sample Output 2

0

Sample Input 3

15 20 17
10111101101100000100
01100000000010000011
01110010111000111000
11001100000111011000
10100001100011100010
01101000101010000101
10110001111110000100
10110011101100101101
01010001110011001001
01010110010001100110
01110100011110011110
01100000100111010010
11001101100111101100
10111100010101111011
00101101011100010000

Sample Output 3

448

Problem Statement

Takahashi is about to play a game where he fights N monsters in order. Initially, Takahashi's health is H and his magic power is M.

For the i-th monster he fights, he can choose one of the following actions:

• Fight without using magic. This can only be chosen when his health is at least A_i, and his health decreases by A_i and the monster is defeated.
• Fight using magic. This can only be chosen when his magic power is at least B_i, and his magic power decreases by B_i and the monster is defeated.

The game ends when all N monsters are defeated or when he cannot take any action. What is the maximum number of monsters he can defeat before the game ends?

Constraints

• 1 \leq N \leq 3000
• 1 \leq H,M \leq 3000
• 1 \leq A_i,B_i \leq 3000
• All input values are integers.

Sample Input 1

4 10 14
5 8
5 6
7 9
99 99

Sample Output 1

3

By taking the following actions, Takahashi can defeat 3 monsters before the game ends.

• Initially, his health is 10 and his magic power is 14.
• Fight the 1st monster without using magic. His health decreases by 5, becoming health 5 and magic power 14.
• Fight the 2nd monster without using magic. His health decreases by 5, becoming health 0 and magic power 14.
• Fight the 3rd monster using magic. His magic power decreases by 9, becoming health 0 and magic power 5.
• For the 4th monster, he cannot choose either action, so the game ends.

Sample Input 2

3 3000 3000
3 3
3 3
3 3

Sample Output 2

3

He may be able to defeat all monsters.

Sample Input 3

10 8 8
2 2
2 3
2 2
1 2
2 3
1 2
3 3
3 2
3 1
3 2

Sample Output 3

9

Problem Statement

There is a circular cake divided into N pieces by cut lines. Each cut line is a line segment connecting the center of the circle to a point on the arc.

The pieces and cut lines are numbered 1, 2, \ldots, N in clockwise order, and piece i has a mass of A_i. Piece 1 is also called piece N + 1.

Cut line i is between pieces i and i + 1, and they are arranged clockwise in this order: piece 1, cut line 1, piece 2, cut line 2, \ldots, piece N, cut line N.

We want to divide this cake among K people under the following conditions. Let w_i be the sum of the masses of the pieces received by the i-th person.

• Each person receives one or more consecutive pieces.
• There are no pieces that no one receives.
• Under the above two conditions, \min(w_1, w_2, \ldots, w_K) is maximized.

Find the value of \min(w_1, w_2, \ldots, w_K) in a division that satisfies the conditions, and the number of cut lines that are never cut in the divisions that satisfy the conditions. Here, cut line i is considered cut if pieces i and i + 1 are given to different people.

Constraints

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

Sample Input 1

5 2
3 6 8 6 4

Sample Output 1

13 1

The following divisions satisfy the conditions:

• Give pieces 2, 3 to one person and pieces 4, 5, 1 to the other. Pieces 2, 3 have a total mass of 14, and pieces 4, 5, 1 have a total mass of 13.
• Give pieces 3, 4 to one person and pieces 5, 1, 2 to the other. Pieces 3, 4 have a total mass of 14, and pieces 5, 1, 2 have a total mass of 13.

The value of \min(w_1, w_2) in divisions satisfying the conditions is 13, and there is one cut line that is not cut in either division: cut line 5.

Sample Input 2

6 3
4 7 11 3 9 2

Sample Output 2

11 1

Sample Input 3

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

Sample Output 3

17 4