Problem Statement

We have a grid with 2 horizontal rows and 2 vertical columns.
Each of the squares is black or white, and there are at least 2 black squares.
The colors of the squares are given to you as strings S_1 and S_2, as follows.

• If the j-th character of S_i is #, the square at the i-th row from the top and j-th column from the left is black.
• If the j-th character of S_i is ., the square at the i-th row from the top and j-th column from the left is white.

You can travel between two different black squares if and only if they share a side.
Determine whether it is possible to travel from every black square to every black square (directly or indirectly) by only passing black squares.

Constraints

• Each of S_1 and S_2 is a string with two characters consisting of # and ..
• S_1 and S_2 have two or more #s in total.

Sample Input 1

##
.#

Sample Output 1

Yes

It is possible to directly travel between the top-left and top-right black squares and between top-right and bottom-right squares.
These two moves enable us to travel from every black square to every black square, so the answer is Yes.

Sample Input 2

.#
#.

Sample Output 2

No

It is impossible to travel between the top-right and bottom-left black squares, so the answer is No.

Problem Statement

Two characters x and y are called similar characters if and only if one of the following conditions is satisfied:

• x and y are the same character.
• One of x and y is 1 and the other is l.
• One of x and y is 0 and the other is o.

Two strings S and T, each of length N, are called similar strings if and only if:

• for all i\ (1\leq i\leq N), the i-th character of S and the i-th character of T are similar characters.

Given two length-N strings S and T consisting of lowercase English letters and digits, determine if S and T are similar strings.

Constraints

• N is an integer between 1 and 100.
• Each of S and T is a string of length N consisting of lowercase English letters and digits.

Sample Input 1

3
l0w
1ow

Sample Output 1

Yes

The 1-st character of S is l, and the 1-st character of T is 1. These are similar characters.

The 2-nd character of S is 0, and the 2-nd character of T is o. These are similar characters.

The 3-rd character of S is w, and the 3-rd character of T is w. These are similar characters.

Thus, S and T are similar strings.

Sample Input 2

3
abc
arc

Sample Output 2

No

The 2-nd character of S is b, and the 2-nd character of T is r. These are not similar characters.

Thus, S and T are not similar strings.

Sample Input 3

4
nok0
n0ko

Sample Output 3

Yes

Problem Statement

I begin with T and end with T, and I am full of T. What am I?

For a string t, define the filling rate as follows:

• If the first and last characters of t are both t and |t| \geq 3: Let x be the number of t in t. Then the filling rate of t is \displaystyle\frac{x-2}{|t|-2}, where |t| denotes the length of t.
• Otherwise: the filling rate of t is 0.

You are given a string S. Find the maximum possible filling rate of a substring of S.

Constraints

• 1 \leq |S| \leq 100
• S is a string consisting of lowercase English letters.

Sample Input 1

attitude

Sample Output 1

0.50000000000000000

ttit is a substring of S, and its filling rate is \displaystyle\frac{3-2}{4-2} = \frac{1}{2}.

There is no substring with a filling rate greater than \frac{1}{2}, so the answer is \frac{1}{2}.

Sample Input 2

ottottott

Sample Output 2

0.66666666666666667

ttottott is a substring of S, and its filling rate is \displaystyle\frac{6-2}{8-2} = \frac{2}{3}.

There is no substring with a filling rate greater than \frac{2}{3}, so the answer is \frac{2}{3}.

Sample Input 3

coffeecup

Sample Output 3

0.00000000000000000

ff is a substring of S, and its filling rate is 0.

There is no substring with a filling rate greater than 0, so the answer is 0.

Problem Statement

Tiles are aligned in N horizontal rows and N vertical columns. Each tile has a grid with A horizontal rows and B vertical columns. On the whole, the tiles form a grid X with (A\times N) horizontal rows and (B\times N) vertical columns.
For 1\leq i,j \leq N, Tile (i,j) denotes the tile at the i-th row from the top and the j-th column from the left.

Each square of X is painted as follows.

• Each tile is either a white tile or a black tile.
• Every square in a white tile is painted white; every square in a black tile is painted black.
• Tile (1,1) is a white tile.
• Two tiles sharing a side have different colors. Here, Tile (a,b) and Tile (c,d) are said to be sharing a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Print the grid X in the format specified in the Output section.

Constraints

• 1 \leq N,A,B \leq 10
• All values in input are integers.

Sample Input 1

4 3 2

Sample Output 1

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

Sample Input 2

5 1 5

Sample Output 2

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

Sample Input 3

4 4 1

Sample Output 3

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

Sample Input 4

1 4 4

Sample Output 4

....
....
....
....

Problem Statement

There are N types of beans, one bean of each type. The i-th type of bean has a deliciousness of A_i and a color of C_i. The beans are mixed and can only be distinguished by color.

You will choose one color of beans and eat one bean of that color. By selecting the optimal color, maximize the minimum possible deliciousness of the bean you eat.

Constraints

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

Sample Input 1

4
100 1
20 5
30 5
40 1

Sample Output 1

40

Note that beans of the same color cannot be distinguished from each other.

You can choose color 1 or color 5.

• There are two types of beans of color 1, with deliciousness of 100 and 40. Thus, the minimum deliciousness when choosing color 1 is 40.
• There are two types of beans of color 5, with deliciousness of 20 and 30. Thus, the minimum deliciousness when choosing color 5 is 20.

To maximize the minimum deliciousness, you should choose color 1, so print the minimum deliciousness in that case: 40.

Sample Input 2

10
68 3
17 2
99 2
92 4
82 4
10 3
100 2
78 1
3 1
35 4

Sample Output 2

35

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Find the number of pairs of integers (i, j) satisfying all of the following conditions:

• 1 \leq i \leq j \leq N
• S_i = S_j
• L \leq j - i \leq R

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq L \leq R \leq N - 1
• N, L, R are integers.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

6 2 4
aabcba

Sample Output 1

2

The pairs of integers satisfying all the conditions in the problem statement are (i, j) = (2, 6), (3, 5), for a total of two pairs.

Sample Input 2

9 3 6
aaaaaaaaa

Sample Output 2

18

Sample Input 3

10 2 6
aabbccaabb

Sample Output 3

6

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 are 2N points placed at equal intervals on a circle, numbered 1 to 2N in a clockwise direction starting from a certain point.

There are also N chords on the circle, with the i-th chord connecting points A_i and B_i. It is guaranteed that all the values A_1,\dots,A_N,B_1,\dots,B_N are distinct.

Determine whether there is an intersection between the chords.

Constraints

• 2\leq N \leq 2\times 10^5
• 1\leq A_i,B_i \leq 2N
• A_1,\dots,A_N,B_1,\dots,B_N are all distinct
• All input values are integers

Sample Input 1

3
1 3
4 2
5 6

Sample Output 1

Yes

As shown in the figure, chord 1 (the line segment connecting points 1 and 3) and chord 2 (the line segment connecting points 4 and 2) intersect, so print Yes.

Sample Input 2

3
6 1
4 3
2 5

Sample Output 2

No

As shown in the figure, there is no intersection between the chords, so print No.

Sample Input 3

4
2 4
3 7
8 6
5 1

Sample Output 3

Yes

Problem Statement

We have an N \times M matrix, whose elements are initially all 0.

Process Q given queries. Each query is in one of the following formats.

• 1 l r x : Add x to every element in the l-th, (l+1)-th, \ldots, and r-th column.
• 2 i x: Replace every element in the i-th row with x.
• 3 i j: Print the (i, j)-th element.

Constraints

• 1 \leq N, M, Q \leq 2 \times 10^5
• Every query is in one of the formats listed in the Problem Statement.
• For each query in the format 1 l r x, 1 \leq l \leq r \leq M and 1 \leq x \leq 10^9.
• For each query in the format 2 i x, 1 \leq i \leq N and 1 \leq x \leq 10^9.
• For each query in the format 3 i j, 1 \leq i \leq N and 1 \leq j \leq M.
• At least one query in the format 3 i j is given.
• All values in input are integers.

Sample Input 1

3 3 9
1 1 2 1
3 2 2
2 3 2
3 3 3
3 3 1
1 2 3 3
3 3 2
3 2 3
3 1 2

Sample Output 1

1
2
2
5
3
4

The matrix transitions as follows.

\begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 2 & 2 & 2 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 4 & 3 \\ 1 & 4 & 3 \\ 2 & 5 & 5 \\ \end{pmatrix}

Sample Input 2

1 1 10
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
3 1 1

Sample Output 2

9000000000

Sample Input 3

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

Sample Output 3

6
5
5
13
10
0