Problem Statement

Takahashi sent a string T consisting of lowercase English letters to Aoki. As a result, Aoki received a string T' consisting of lowercase English letters.

T' may have been altered from T. Specifically, exactly one of the following four conditions is known to hold.

• T' is equal to T.
• T' is a string obtained by inserting one lowercase English letter at one position (possibly the beginning and end) in T.
• T' is a string obtained by deleting one character from T.
• T' is a string obtained by changing one character in T to another lowercase English letter.

You are given the string T' received by Aoki and N strings S_1, S_2, \ldots, S_N consisting of lowercase English letters. Find all the strings among S_1, S_2, \ldots, S_N that could equal the string T sent by Takahashi.

Constraints

• N is an integer.
• 1 \leq N \leq 5 \times 10^5
• S_i and T' are strings of length between 1 and 5 \times 10^5, inclusive, consisting of lowercase English letters.
• The total length of S_1, S_2, \ldots, S_N is at most 5 \times 10^5.

Sample Input 1

5 ababc
ababc
babc
abacbc
abdbc
abbac

Sample Output 1

4
1 2 3 4

Among S_1, S_2, \ldots, S_5, the strings that could be equal to T are S_1, S_2, S_3, S_4, as explained below.

• S_1 could be equal to T, because T' = ababc is equal to S_1 = ababc.
• S_2 could be equal to T, because T' = ababc is obtained by inserting the letter a at the beginning of S_2 = babc.
• S_3 could be equal to T, because T' = ababc is obtained by deleting the fourth character c from S_3 = abacbc.
• S_4 could be equal to T, because T' = ababc is obtained by changing the third character d in S_4 = abdbc to b.
• S_5 could not be equal to T, because if we take S_5 = abbac as T, then T' = ababc does not satisfy any of the four conditions in the problem statement.

Sample Input 2

1 aoki
takahashi

Sample Output 2

0

Sample Input 3

9 atcoder
atoder
atcode
athqcoder
atcoder
tacoder
jttcoder
atoder
atceoder
atcoer

Sample Output 3

6
1 2 4 7 8 9

Problem Statement

There are N people, each of whom is either a child or an adult. The i-th person has a weight of W_i.
Whether each person is a child or an adult is specified by a string S of length N consisting of 0 and 1.
If the i-th character of S is 0, then the i-th person is a child; if it is 1, then the i-th person is an adult.

When Takahashi the robot is given a real number X, Takahashi judges a person with a weight less than X to be a child and a person with a weight more than or equal to X to be an adult.
For a real value X, let f(X) be the number of people whom Takahashi correctly judges whether they are children or adults.

Find the maximum value of f(X) for all real values of X.

Constraints

• 1\leq N\leq 2\times 10^5
• S is a string of length N consisting of 0 and 1.
• 1\leq W_i\leq 10^9
• N and W_i are integers.

Sample Input 1

5
10101
60 45 30 40 80

Sample Output 1

4

When Takahashi is given X=50, it judges the 2-nd, 3-rd, and 4-th people to be children and the 1-st and 5-th to be adults.
In reality, the 2-nd and 4-th are children, and the 1-st, 3-rd, and 5-th are adults, so the 1-st, 2-nd, 4-th, and 5-th people are correctly judged. Thus, f(50)=4.

This is the maximum since there is no X that judges correctly for all 5 people. Thus, 4 should be printed.

Sample Input 2

3
000
1 2 3

Sample Output 2

3

For example, X=10 achieves the maximum value f(10)=3.
Note that the people may be all children or all adults.

Sample Input 3

5
10101
60 50 50 50 60

Sample Output 3

4

For example, X=55 achieves the maximum value f(55)=4.
Note that there may be multiple people with the same weight.

Problem Statement

There is a rectangular cake with some strawberries on the xy-plane. The cake occupies the rectangular area \lbrace (x, y) : 0 \leq x \leq W, 0 \leq y \leq H \rbrace.

There are N strawberries on the cake, and the coordinates of the i-th strawberry are (p_i, q_i) for i = 1, 2, \ldots, N. No two strawberries have the same coordinates.

Takahashi will cut the cake into several pieces with a knife, as follows.

• First, cut the cake along A different lines parallel to the y-axis: lines x = a_1, x = a_2, \ldots, x = a_A.
• Next, cut the cake along B different lines parallel to the x-axis: lines y = b_1, y = b_2, \ldots, y = b_B.

As a result, the cake will be divided into (A+1)(B+1) rectangular pieces. Takahashi will choose just one of these pieces to eat. Print the minimum and maximum possible numbers of strawberries on the chosen piece.

Here, it is guaranteed that there are no strawberries along the edges of the final pieces. For a more formal description, refer to the constraints below.

Constraints

• 3 \leq W, H \leq 10^9
• 1 \leq N \leq 2 \times 10^5
• 0 \lt p_i \lt W
• 0 \lt q_i \lt H
• i \neq j \implies (p_i, q_i) \neq (p_j, q_j)
• 1 \leq A, B \leq 2 \times 10^5
• 0 \lt a_1 \lt a_2 \lt \cdots \lt a_A \lt W
• 0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H
• p_i \not \in \lbrace a_1, a_2, \ldots, a_A \rbrace
• q_i \not \in \lbrace b_1, b_2, \ldots, b_B \rbrace
• All input values are integers.

Sample Input 1

7 6
5
6 1
3 1
4 2
1 5
6 2
2
2 5
2
3 4

Sample Output 1

0 2

There are nine pieces in total: six with zero strawberries, one with one strawberry, and two with two strawberries. Therefore, when choosing just one of these pieces to eat, the minimum possible number of strawberries on the chosen piece is 0, and the maximum possible number is 2.

Sample Input 2

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

Sample Output 2

1 1

Each piece has one strawberry on it.

Problem Statement

You are given a length-N sequence A=(A_1,A_2,\dots,A_N) consisting of 0, 1, and 2, and a length-N string S=S_1S_2\dots S_N consisting of M, E, and X.

Find the sum of \text{mex}(A_i,A_j,A_k) over all tuples of integers (i,j,k) such that 1 \leq i < j < k \leq N and S_iS_jS_k= MEX. Here, \text{mex}(A_i,A_j,A_k) denotes the minimum non-negative integer that equals neither A_i,A_j, nor A_k.

Constraints

• 3\leq N \leq 2\times 10^5
• N is an integer.
• A_i \in \lbrace 0,1,2\rbrace
• S is a string of length N consisting of M, E, and X.

Sample Input 1

4
1 1 0 2
MEEX

Sample Output 1

3

The tuples (i,j,k)\ (1 \leq i < j < k \leq N) such that S_iS_jS_k = MEX are the following two: (i,j,k)=(1,2,4),(1,3,4). Since \text{mex}(A_1,A_2,A_4)=\text{mex}(1,1,2)=0 and \text{mex}(A_1,A_3,A_4)=\text{mex}(1,0,2)=3, the answer is 0+3=3.

Sample Input 2

3
0 0 0
XXX

Sample Output 2

0

Sample Input 3

15
1 1 2 0 0 2 0 2 0 0 0 0 0 2 2
EXMMXXXEMEXEXMM

Sample Output 3

13

Problem Statement

Let us define a correct parenthesis sequence as a string that satisfies one of the following conditions.

• It is an empty string.
• It is a concatenation of (, A, ), in this order, for some correct parenthesis sequence A.
• It is a concatenation of A, B, in this order, for some correct parenthesis sequences A and B.

We have a string S of length N consisting of ( and ).

Given Q queries \text{Query}_1,\text{Query}_2,\ldots,\text{Query}_Q, process them in order. There are two kinds of queries, with the following formats and content.

• 1 l r: Swap the l-th and r-th characters of S.
• 2 l r: Determine whether the contiguous substring from the l-th through the r-th character is a correct parenthesis sequence.

Constraints

• 1 \leq N,Q \leq 2 \times 10^5
• S is a string of length N consisting of ( and ).
• 1 \leq l < r \leq N
• N,Q,l,r are all integers.
• Each query is in the format 1 l r or 2 l r.
• There is at least one query in the format 2 l r.

Sample Input 1

5 3
(())(
2 1 4
2 1 2
2 4 5

Sample Output 1

Yes
No
No

In the first query, (()) is a correct parenthesis sequence.

In the second query, (( is not a correct parenthesis sequence.

In the third query, )( is not a correct parenthesis sequence.

Sample Input 2

5 3
(())(
2 1 4
1 1 4
2 1 4

Sample Output 2

Yes
No

In the first query, (()) is a correct parenthesis sequence.

In the second query, S becomes )()((.

In the third query, )()( is not a correct parenthesis sequence.

Sample Input 3

8 8
(()(()))
2 2 7
2 2 8
1 2 5
2 3 4
1 3 4
1 3 5
1 1 4
1 6 8

Sample Output 3

Yes
No
No