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

In AtCoder Land, there are N popcorn stands numbered 1 to N. They have M different flavors of popcorn, labeled 1, 2, \dots, M, but not every stand sells all flavors of popcorn.

Takahashi has obtained information about which flavors of popcorn are sold at each stand. This information is represented by N strings S_1, S_2, \dots, S_N of length M. If the j-th character of S_i is o, it means that stand i sells flavor j of popcorn. If it is x, it means that stand i does not sell flavor j. Each stand sells at least one flavor of popcorn, and each flavor of popcorn is sold at least at one stand.

Takahashi wants to try all the flavors of popcorn but does not want to move around too much. Determine the minimum number of stands Takahashi needs to visit to buy all the flavors of popcorn.

Constraints

• N and M are integers.
• 1 \leq N, M \leq 10
• Each S_i is a string of length M consisting of o and x.
• For every i (1 \leq i \leq N), there is at least one o in S_i.
• For every j (1 \leq j \leq M), there is at least one i such that the j-th character of S_i is o.

Sample Input 1

3 5
oooxx
xooox
xxooo

Sample Output 1

2

By visiting the 1st and 3rd stands, you can buy all the flavors of popcorn. It is impossible to buy all the flavors from a single stand, so the answer is 2.

Sample Input 2

3 2
oo
ox
xo

Sample Output 2

1

Sample Input 3

8 6
xxoxxo
xxoxxx
xoxxxx
xxxoxx
xxoooo
xxxxox
xoxxox
oxoxxo

Sample Output 3

3

Problem Statement

Takahashi has 10^{100} flower pots. Initially, he is not growing any plants.

You are given Q queries to process in order.

There are three types of queries as follows.

• 1: Prepare one empty flower pot and put a plant in it. Here, the plant's height is 0.
• 2 T: Wait for T days. During this time, the height of every existing plants increases by T.
• 3 H: Harvest all plants with a height of at least H, and output the number of plants harvested. The harvested plants are removed from their flower pots.

Assume that performing queries of the first and third types takes zero time.

Constraints

• 1 \leq Q \leq 2 \times 10^{5}
• 1 \leq T,H \leq 10^{9}
• There is at least one query of the third type.
• All input values are integers.

Sample Input 1

6
1
2 15
1
3 10
2 20
3 20

Sample Output 1

1
1

Queries are processed in the following order:

• In the first query, a plant of height 0 is planted.
• In the second query, the height of the plant increases to 15.
• In the third query, another plant of height 0 is planted. Now there is one plant of height 15 and one plant of height 0.
• In the fourth query, all plants with height at least 10 are harvested. Here, one plant of height 15 gets harvested, and one plant of height 0 remains. Since one plant was harvested, print 1 on the first line.
• In the fifth query, the height of the remaining plant increases to 20.
• In the sixth query, all plants with height at least 20 are harvested. Here, one plant of height 20 gets harvested. Thus, print 1 on the second line.

Sample Input 2

15
1
1
2 226069413
3 1
1
1
2 214168203
1
3 214168203
1
1
1
2 314506461
2 245642315
3 1

Sample Output 2

2
2
4

Problem Statement

You are given a sequence A of non-negative integers of length N, and an integer K. It is guaranteed that the binomial coefficient \dbinom{N}{K} is at most 10^6.

When choosing K distinct elements from A, find the maximum possible value of the XOR of the K chosen elements.

That is, find \underset{1\leq i_1\lt i_2\lt \ldots\lt i_K\leq N}{\max} A_{i_1}\oplus A_{i_2}\oplus \ldots \oplus A_{i_K}.

Constraints

• 1\leq K\leq N\leq 2\times 10^5
• 0\leq A_i<2^{60}
• \dbinom{N}{K}\leq 10^6
• All input values are integers.

Sample Input 1

4 2
3 2 6 4

Sample Output 1

7

Here are six ways to choose two distinct elements from (3,2,6,4).

• (3,2): The XOR is 3\oplus 2 = 1.
• (3,6): The XOR is 3\oplus 6 = 5.
• (3,4): The XOR is 3\oplus 4 = 7.
• (2,6): The XOR is 2\oplus 6 = 4.
• (2,4): The XOR is 2\oplus 4 = 6.
• (6,4): The XOR is 6\oplus 4 = 2.

Hence, the maximum possible value is 7.

Sample Input 2

10 4
1516 1184 1361 2014 1013 1361 1624 1127 1117 1759

Sample Output 2

2024

Problem Statement

You are given a string S = S_1 S_2 S_3 \dots S_{|S|} consisting of uppercase and lowercase English letters, (, and ).
The parentheses in the string S are properly matched.

Repeat the following operation until no more operations can be performed:

• First, select one pair of integers (l, r) that satisfies all of the following conditions:
  • l < r
  • S_l = (
  • S_r = )
  • Each of the characters S_{l+1}, S_{l+2}, \dots, S_{r-1} is an uppercase or lowercase English letter.
• Let T = \overline{S_{r-1} S_{r-2} \dots S_{l+1}}.
  • Here, \overline{x} denotes the string obtained by toggling the case of each character in x (uppercase to lowercase and vice versa).
• Then, delete the l-th through r-th characters of S and insert T at the position where the deletion occurred.

Refer to the sample inputs and outputs for clarification.

It can be proved that it is possible to remove all (s and )s from the string using the above operations, and the final string is independent of how and in what order the operations are performed.
Determine the final string.

Constraints

• 1 \le |S| \le 5 \times 10^5
• S consists of uppercase and lowercase English letters, (, and ).
• The parentheses in S are properly matched.

Sample Input 1

((A)y)x

Sample Output 1

YAx

Let us perform the operations for S = ((A)y)x.

• Choose l=2 and r=4. The substring (A) is removed and replaced with a.
  • After this operation, S = (ay)x.
• Choose l=1 and r=4. The substring (ay) is removed and replaced with YA.
  • After this operation, S = YAx.

After removing the parentheses, the string becomes YAx, which should be printed.

Sample Input 2

((XYZ)n(X(y)Z))

Sample Output 2

XYZNXYZ

Let us perform the operations for S = ((XYZ)n(X(y)Z)).

• Choose l=10 and r=12. The substring (y) is removed and replaced with Y.
  • After this operation, S = ((XYZ)n(XYZ)).
• Choose l=2 and r=6. The substring (XYZ) is removed and replaced with zyx.
  • After this operation, S = (zyxn(XYZ)).
• Choose l=6 and r=10. The substring (XYZ) is removed and replaced with zyx.
  • After this operation, S = (zyxnzyx).
• Choose l=1 and r=9. The substring (zyxnzyx) is removed and replaced with XYZNXYZ.
  • After this operation, S = XYZNXYZ.

After removing the parentheses, the string becomes XYZNXYZ, which should be printed.

Sample Input 3

(((()))(()))(())

Sample Output 3

The final outcome may be an empty string.

Sample Input 4

dF(qT(plC())NnnfR(GsdccC))PO()KjsiI((ysA)eWW)ve

Sample Output 4

dFGsdccCrFNNnplCtQPOKjsiIwwEysAve