Problem Statement

In AtCoder Country where Takahashi lives, there is a strange law that "a person who possesses A or more candies must possess B or more cookies."

Takahashi possesses C candies and D cookies. Determine whether Takahashi is violating this law.

Constraints

• 1\leq A,B,C,D \leq 100
• All input values are integers.

Sample Input 1

10 20 30 40

Sample Output 1

No

In AtCoder Country, there is a law that "a person who possesses 10 or more candies must possess 20 or more cookies."

Takahashi possesses 30 candies and 40 cookies, so he is not violating this law.

Sample Input 2

10 20 30 4

Sample Output 2

Yes

Sample Input 3

100 100 1 1

Sample Output 3

No

Problem Statement

There is a grid with N rows and N columns. The cell at the i-th row from the top and j-th column from the left is painted black if S_{i,j} is #, and white if it is ..

How many distinct patterns of painted cells can be obtained by extracting a region of M rows and M columns from this grid?

Constraints

• 1\leq M \leq N \leq 10
• N and M are integers.
• S_{i,j} is . or #.

Sample Input 1

3 2
...
###
#.#

Sample Output 1

3

The state of the given grid is as shown in the left figure below.
There are four ways to extract a region of two rows and two columns from this grid as shown in the right figure below, and there are three distinct patterns of painted cells.

Sample Input 2

10 3
..#.......
.###......
.#.#......
#####.....
#...#.....
......####
......#..#
......#...
......#..#
......####

Sample Output 2

36

Problem Statement

In AtCoder Country, there is a rule that "a truck driver must take a break of at least B minutes when driving for A minutes or more."

You are given a string S of length N consisting of a and b, and positive integers A and B. Find the number of integer pairs (l,r) that satisfy all of the following conditions.

• 1\leq l \leq r \leq N
• The number of a in the substring from the l-th character through the r-th character of S is greater than or equal to A.
• The number of b in the substring from the l-th character through the r-th character of S is less than B.

Constraints

• 1\leq N \leq 3\times 10^5
• 1 \leq A,B \leq N
• S is a string of length N consisting of a and b.
• All input numbers are integers.

Sample Input 1

11 4 2
abbaaabaaba

Sample Output 1

3

The pairs (l,r) that satisfy the conditions are (4,8),(4,9),(5,9), which is three pairs.

Sample Input 2

13 1 2
bbbbbbbbbbbbb

Sample Output 2

0

There are no pairs (l,r) that satisfy the conditions.

Problem Statement

There is a number line, and initially person 0 is standing alone at coordinate 0.

From now on, persons 1,2,\dots,N will arrive in this order and stand on the number line.
Person i stands at coordinate X_i. Here, X_i \ge 1, and X_i is distinct for all persons.

Each time a person arrives, answer the following question.

• Suppose that currently r+1 persons 0,1,\dots,r are standing on the number line.
• Here, define d_i as the distance to the nearest other person from person i.
  • More formally, \displaystyle d_i = \min_{0 \le j \le r, j \neq i} \vert X_i - X_j \vert.
• Find the sum of this d, that is, \displaystyle \sum_{i=0}^r d_i.

Constraints

• All input values are integers.
• 1 \le N \le 5 \times 10^5
• 1 \le X_i \le 10^9
• X_i \neq X_j if i \neq j.

Sample Input 1

10
5 2 7 4 108728325 390529120 597713292 322456626 845148281 812604915

Sample Output 1

10
7
8
8
108728326
390529121
523096670
452057486
699492475
517144218

In this input, 10 persons arrive.
The first four persons are explained below.

• When person 1 arrives, there are persons at coordinates 0,5.
  • The required value is 5+5=10.
• When person 2 arrives, there are persons at coordinates 0,2,5.
  • The required value is 2+2+3=7.
• When person 3 arrives, there are persons at coordinates 0,2,5,7.
  • The required value is 2+2+2+2=8.
• When person 4 arrives, there are persons at coordinates 0,2,4,5,7.
  • The required value is 2+2+1+1+2=8.

Problem Statement

You are given strings A and B of equal length consisting of 0 and 1.

You can perform the following operation on A zero or more times.

• Move the first character of A to the end.

Find the minimum number of operations required to make A=B.
If it is impossible to make A=B no matter how you operate, print -1 instead.

You are given T test cases; find the answer for each of them.

Constraints

• 1 \le T \le 10000
• A and B are strings consisting of 0 and 1.
• 2 \le |A|=|B| \le 10^6
• For a single input, the sum of |A| does not exceed 10^6.

Sample Input 1

5
1010001
1000110
000
111
01010
01010
0101
0011
100001101110000001010110110001
101100011000011011100000010101

Sample Output 1

2
-1
0
-1
22

This input contains five test cases.

• For the first test case, A= 1010001 and B= 1000110.
  • By performing the operation on A twice, A becomes 1010001 \rightarrow 0100011 \rightarrow 1000110, which makes A=B.
• For the second test case, no matter how you perform the operation, you cannot change 000 to 111.
• For the third test case, A=B from the beginning.

Problem Statement

You are given an integer N and a string S of length N-1 consisting of L and R.

Consider writing integers into N cells arranged in a row so that the following conditions are satisfied:

• Every cell has one integer written on it.
• Every integer 1,2,\dots,N appears in exactly one cell.
• When the i-th character of S is L, i+1 is written to the left of i.
• When the i-th character of S is R, i+1 is written to the right of i.

Let C_i be the number of integers that can be written in the i-th cell from the left. Find C_1,C_2,\dots,C_N.

You are given T test cases; find the answer for each of them.

Constraints

• 1 \le T \le 20000
• 2 \le N \le 3 \times 10^5
• S is a string of length N-1 consisting of L and R.
• For a single input, the sum of N does not exceed 3 \times 10^5.

Sample Input 1

5
5
RLLR
3
RL
2
L
3
RR
20
RLLLLLLLLRLRRLLLRLR

Sample Output 1

2 4 3 4 2
2 2 1
1 1
1 1 1
5 9 13 14 15 17 18 19 19 20 20 19 19 18 17 16 14 12 9 5

This input contains five test cases.

• For the first test case, there are 11 possible ways to fill the cells as follows:
  • (1,4,3,2,5)
  • (1,4,3,5,2)
  • (1,4,5,3,2)
  • (4,1,3,2,5)
  • (4,1,3,5,2)
  • (4,1,5,3,2)
  • (4,3,1,2,5)
  • (4,3,1,5,2)
  • (4,3,5,1,2)
  • (4,5,1,3,2)
  • (4,5,3,1,2)
• From this, each value of C_i is determined as follows:
  • The integers that can be written in the 1-st cell from the left are 1,4, which is two integers.
  • The integers that can be written in the 2-nd cell from the left are 1,3,4,5, which is four integers.
  • The integers that can be written in the 3-rd cell from the left are 1,3,5, which is three integers.
  • The integers that can be written in the 4-th cell from the left are 1,2,3,5, which is four integers.
  • The integers that can be written in the 5-th cell from the left are 2,5, which is two integers.
• For the second test case, there are two possible ways to fill the cells as follows:
  • (1,3,2)
  • (3,1,2)
• For the third test case, there is one possible way to fill the cells as follows:
  • (2,1)
• For the fourth test case, there is one possible way to fill the cells as follows:
  • (1,2,3)

Problem Statement

There are N sets S_1, \ldots,S_N. Initially, all sets are empty.

You are given Q queries in the following formats. Process them in order.

• Type 1: Given as 1 L R x. For each S_i satisfying L \leq i \leq R, add x.
• Type 2: Given as 2 L R x. For each S_i satisfying L \leq i \leq R, remove x.
• Type 3: Given as 3 L R. Find the maximum number of elements among S_i satisfying L \leq i \leq R, and the number of sets that achieve this maximum.

Constraints

• 1\leq N \leq 3\times 10^5
• 1\leq Q \leq 3\times 10^5
• For each query, 1 \leq L \leq R \leq N.
• For type 1,2 queries, 1 \leq x \leq 60.
• All input values are integers.

Sample Input 1

4 7
1 1 2 10
1 2 4 20
3 1 3
2 1 2 20
1 2 3 10
3 1 2
3 1 4

Sample Output 1

2 1
1 2
2 1

• Initially (S_1,S_2,S_3,S_4)=(\lbrace\rbrace,\lbrace\rbrace,\lbrace\rbrace,\lbrace\rbrace).
• The 1-st query adds 10 to S_1,S_2, resulting in (S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10\rbrace,\lbrace\rbrace,\lbrace\rbrace).
• The 2-nd query adds 20 to S_2,S_3,S_4, resulting in (S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10,20\rbrace,\lbrace 20\rbrace,\lbrace 20\rbrace).
• For the 3-rd query, the maximum number of elements among S_1,S_2,S_3 is 2 achieved by S_2, so print 2 1.
• The 4-th query removes 20 from S_1,S_2, resulting in (S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10\rbrace,\lbrace 20\rbrace,\lbrace 20\rbrace).
• The 5-th query adds 10 to S_2,S_3, resulting in (S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10\rbrace,\lbrace 10,20\rbrace,\lbrace 20\rbrace).
• For the 6-th query, the maximum number of elements among S_1,S_2 is 1 achieved by S_1,S_2, so print 1 2.
• For the 7-th query, the maximum number of elements among S_1,S_2,S_3,S_4 is 2 achieved by S_3, so print 2 1.