Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N and an integer X.
Determine whether X is contained in A.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le A_i \le 100
• 1 \le X \le 100

Sample Input 1

5
3 1 4 1 5
4

Sample Output 1

Yes

We have A=(3,1,4,1,5) and X=4; X is contained in A.

Sample Input 2

4
100 100 100 100
100

Sample Output 2

Yes

X may be contained in A multiple times.

Sample Input 3

6
2 3 5 7 11 13
1

Sample Output 3

No

Problem Statement

There is a linear warehouse, which stores an even number of packages.
The layout of the warehouse is represented by a string S.
The warehouse has |S| sections, numbered 1,2,\dots,|S|, and the string S describes them as follows:

• When the i-th character of S is #, one package is placed in section i.
• When the i-th character of S is ., no package is placed in section i.

The warehouse has a robot, which repeats the following action until there are no more packages in the warehouse:

• Collect two packages from the sections with the smallest section numbers among the sections containing packages. The collected packages are carried out of the warehouse.

For each iteration, determine which sections of the warehouse the two packages that were carried out were originally located.

Constraints

• S is a string consisting of # and . with length between 2 and 1000, inclusive.
• The warehouse stores an even number of packages.
• The warehouse stores at least two packages.

Sample Input 1

.#.##..##.#.###....#

Sample Output 1

2,4
5,8
9,11
13,14
15,20

Packages are stored in sections 2,4,5,8,9,11,13,14,15,20.

• In the 1st iteration, packages from sections 2,4 are carried out.
• In the 2nd iteration, packages from sections 5,8 are carried out.
• In the 3rd iteration, packages from sections 9,11 are carried out.
• In the 4th iteration, packages from sections 13,14 are carried out.
• In the 5th iteration, packages from sections 15,20 are carried out.

Problem Statement

There are N types of chemicals 1,2,\dots,N. Your goal is to create a state where all of them are mixed.
You are given a string S of length 2^N-1 consisting of 0 and 1, which represents the following information:

• First, define state i (1 \le i \le 2^N-1) where one or more types of chemicals are mixed as follows:
  • When the k-th digit (1 \le k \le N) from the bottom in the binary representation of i is 1, and only then, chemical k is included.
  • For example, 13 in binary is 1101_{(2)}, so state 13 represents a state where chemicals 1,3,4 are mixed.
• When the i-th character of S is 0, state i is safe.
• When the i-th character of S is 1, state i is dangerous.

You mix chemicals using the following operation:

• First, prepare an empty bottle.
• Next, repeat the following:
  • Choose one type of chemical that has not yet been poured into the bottle and pour it into the bottle.
  • At this time, the chemicals mixed in the bottle must not be in a dangerous state.

Determine whether this operation can create a state where all chemicals are mixed.

You are given T test cases; solve each of them.

Constraints

• T is an integer between 1 and 40000, inclusive.
• N is an integer between 1 and 18, inclusive.
• S is a string of length 2^N-1 consisting of 0 and 1.
• The sum of |S| = 2^N-1 in each input does not exceed 5 \times 10^5.

Sample Input 1

5
3
0010000
3
0010110
1
1
2
100
4
001110010101110

Sample Output 1

Yes
No
No
Yes
Yes

This input contains five test cases.

The 1st case is as follows:

• There are three types of chemicals.
• Only state 3 where chemicals 1,2 are mixed is dangerous, and the other states are safe.
• For example, you can create a state where all chemicals are mixed with the following procedure:
  • First, pour chemical 2 into the bottle. Only chemical 2 is mixed in the bottle, which is state 2, so it is safe.
  • Next, pour chemical 3 into the bottle. Chemicals 2,3 are mixed in the bottle, which is state 6, so it is safe.
  • Finally, pour chemical 1 into the bottle. Chemicals 1,2,3 are mixed in the bottle, which is state 7, so it is safe.

The 2nd case is as follows:

• There are three types of chemicals.
• State 3 where chemicals 1,2 are mixed, state 5 where chemicals 1,3 are mixed, and state 6 where chemicals 2,3 are mixed are dangerous, and the other states are safe.
• For this case, it is impossible to create a state where all chemicals are mixed.

The 3rd case is as follows:

• There is one type of chemical.
• Since state 1 where only chemical 1 is mixed is dangerous, it is impossible to create a state where all chemicals are mixed.

Problem Statement

The setting of this problem is similar to Problem G. It differs from Problem G in the target of maximization and some constraints.

There is a mysterious cola shop. This shop does not sell cola directly, but provides an exchange service between empty cola bottles and new bottled cola.

Initially, Takahashi has N bottled colas, and from now on he can choose and take one of the following actions any number of times (possibly zero):

• Drink 1 bottled cola that he has. The number of bottled colas he has decreases by 1, and the number of empty bottles increases by 1. (If he has no bottled cola before the action, he cannot take this action.)
• Choose an integer i between 1 and M, inclusive. Give A_i empty bottles to the cola shop, and receive B_i bottled colas and 1 commemorative sticker in return. (He cannot choose i such that the number of empty bottles he has before the action is less than A_i. If there is no i that can be chosen, he cannot take this action.)

Takahashi loves stickers. When he acts optimally, what is the maximum number of stickers he can obtain?

He initially has no empty bottles and no stickers.

Constraints

• 1\leq N \leq 10^{18}
• 1\leq M \leq 2\times 10^5
• 1\leq B_i < A_i \leq 10^{18}
• All input values are integers.

Sample Input 1

5 3
5 1
4 3
3 1

Sample Output 1

3

Consider the following actions:

• Initially, Takahashi has 5 bottled colas.
• Repeat drinking 1 bottled cola 5 times. Takahashi has 5 empty bottles.
• Make an exchange with i=2, giving 4 empty bottles in exchange for 3 bottled colas and 1 sticker. Takahashi has 3 bottled colas, 1 empty bottle, and 1 sticker.
• Repeat drinking 1 bottled cola 3 times. Takahashi has 4 empty bottles and 1 sticker.
• Make an exchange with i=2, giving 4 empty bottles in exchange for 3 bottled colas and 1 sticker. Takahashi has 3 bottled colas and 2 stickers.
• Repeat drinking 1 bottled cola 3 times. Takahashi has 3 empty bottles and 2 stickers.
• Make an exchange with i=3, giving 3 empty bottles in exchange for 1 bottled cola and 1 sticker. Takahashi has 1 bottled cola and 3 stickers.

After these actions are completed, Takahashi has 3 stickers. No matter how he acts, he cannot obtain 4 or more stickers, so the answer is 3.

Sample Input 2

3 3
5 1
5 1
4 2

Sample Output 2

0

He can only drink the bottled colas he originally had.

Sample Input 3

415 8
327 299
413 396
99 67
108 51
195 98
262 180
250 175
234 187

Sample Output 3

11

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. Some coins are placed on each cell, and there are A_{i,j} coins on cell (i,j).

Takahashi is initially at cell (1,1) and has x coins. Over the next H+W-1 days, several events will occur. On the k-th day (1\leq k\leq H+W-1), the following things happen in order:

1. Takahashi collects all the coins placed on the cell where he is currently located.
2. Hungry Takahashi consumes P_k coins from his hand to buy food. However, if he has fewer than P_k coins, he cannot buy food and collapses from hunger.
3. If k < H+W-1, Takahashi moves either one cell right or one cell down. He cannot leave the grid. If k=H+W-1, he does nothing.

When there exists a way for Takahashi to finish the next H+W-1 days without ever collapsing from hunger, find the minimum non-negative integer x that can be the number of coins Takahashi initially has.

Constraints

• H,W\geq 1
• H\times W \leq 2\times 10^5
• 1\leq A_{i,j}\leq 10^9
• 1\leq P_k\leq 10^9
• All input values are integers.

Sample Input 1

2 2
3 2
4 1
1 3 6

Sample Output 1

2

When x=2, Takahashi can act as follows to avoid collapsing from hunger:

• Initially, he is at cell (1,1) and has 2 coins.
• Day 1:
  1. He collects 3 coins placed on cell (1,1), so he has 5 coins.
  2. He consumes 1 coin to buy food, so he has 4 coins.
  3. He moves to cell (2,1) which is 1 below.
• Day 2:
  1. He collects 4 coins placed on cell (2,1), so he has 8 coins.
  2. He consumes 3 coins to buy food, so he has 5 coins.
  3. He moves to cell (2,2) which is 1 to the right.
• Day 3:
  1. He collects 1 coin placed on cell (2,2), so he has 6 coins.
  2. He consumes 6 coins to buy food, so he has 0 coins.

When x is 1 or less, Takahashi will collapse from hunger at some point no matter how he acts. Therefore, the answer is 2.

Sample Input 2

1 1
5
3

Sample Output 2

0

Even if Takahashi initially has no coins, he will not collapse from hunger.

Sample Input 3

4 7
35 29 36 88 58 15 25
99 7 49 61 67 4 57
96 92 3 49 49 36 90
72 89 40 44 24 53 45
55 43 23 71 77 6 94 19 27 21

Sample Output 3

20

Problem Statement

There is a string S of length N consisting of lowercase English letters. Process a total of Q queries as follows:

• Type 1 : Change the i-th character of S to x.
• Type 2 : Let t be the substring of the current S from the l-th character through the r-th character. Find f(t) defined as follows for this string:
  • f(t) is the maximum length of consecutive identical characters in t.
  • More precisely, when choosing integers a,b such that 1 \le a \le b \le |t| and all characters from the a-th through the b-th character of t are equal, f(t) is the maximum possible value of b-a+1.
  • For example, f( aaaccbbbb )=4, f( bbaaabb )=3, f( x )=1.

Constraints

• N is an integer between 1 and 5 \times 10^5, inclusive.
• S is a string of length N consisting of lowercase English letters.
• Q is an integer between 1 and 5 \times 10^5, inclusive.
• Type 1 queries satisfy the following constraints:
  • i is an integer between 1 and N, inclusive.
  • x is a lowercase English letter.
• Type 2 queries satisfy the following constraints:
  • l,r are integers satisfying 1 \le l \le r \le N.

Sample Input 1

10 5
babaacczcc
2 1 4
1 3 a
2 1 10
1 8 c
2 1 10

Sample Output 1

1
4
5

This input contains five queries.

• Initially, the string S is babaacczcc.
• The 1st query is type 2 with l=1,r=4.
  • The extracted string is baba, and f( baba )=1.
• The 2nd query is type 1 with i=3,x= a.
  • The string S after the change is baaaacczcc.
• The 3rd query is type 2 with l=1,r=10.
  • The extracted string is baaaacczcc, and f( baaaacczcc )=4.
• The 4th query is type 1 with i=8,x= c.
  • The string S after the change is baaaaccccc.
• The 5th query is type 2 with l=1,r=10.
  • The extracted string is baaaaccccc, and f( baaaaccccc )=5.

Sample Input 2

1 1
a
1 1 z

Sample Output 2

The output may be empty.

Problem Statement

The setting of this problem is similar to Problem D. It differs from Problem D in the target of maximization and some constraints.

There is a mysterious cola shop. This shop does not sell cola directly, but provides an exchange service between empty cola bottles and new bottled cola.

Initially, Takahashi has N bottled colas, and from now on he can choose and take one of the following actions any number of times (possibly zero):

• Drink 1 bottled cola that he has. The number of bottled colas he has decreases by 1, and the number of empty bottles increases by 1. (If he has no bottled cola before the action, he cannot take this action.)
• Choose an integer i between 1 and M, inclusive. Give A_i empty bottles to the cola shop, and receive B_i bottled colas in return. (He cannot choose i such that the number of empty bottles he has before the action is less than A_i. If there is no i that can be chosen, he cannot take this action.)

Takahashi loves cola. When he acts optimally, what is the maximum number of colas he can drink?

He initially has no empty bottles.

Constraints

• 1\leq N \leq 10^{15}
• 1\leq M \leq 2\times 10^5
• 1\leq B_i < A_i \leq 300
• All input values are integers.

Sample Input 1

5 3
5 4
5 1
4 2

Sample Output 1

11

Consider the following actions:

• Initially, Takahashi has 5 bottled colas.
• Repeat drinking 1 bottled cola 5 times. Takahashi has 5 empty bottles.
• Make an exchange with i=1, giving 5 empty bottles in exchange for 4 bottled colas. Takahashi has 4 bottled colas.
• Repeat drinking 1 bottled cola 4 times. Takahashi has 4 empty bottles.
• Make an exchange with i=3, giving 4 empty bottles in exchange for 2 bottled colas. Takahashi has 2 bottled colas.
• Repeat drinking 1 bottled cola 2 times. Takahashi has 2 empty bottles.

At this point, Takahashi has drunk a total of 5+4+2=11 colas. No matter how he acts, he cannot drink 12 or more colas, so the answer is 11.

Sample Input 2

3 3
5 1
4 2
5 1

Sample Output 2

3

He can only drink the bottled colas he originally had.

Sample Input 3

925532735634776 8
91 40
273 265
286 153
155 126
92 83
291 228
216 90
234 9

Sample Output 3

31583804603529464