Problem Statement

There is a grid with N horizontal rows and N vertical columns, where each square is painted white or black.
The state of the grid is represented by N strings, S_i. If the j-th character of S_i is #, the square at the i-th row from the top and the j-th column from the left is painted black. If the character is ., then the square is painted white.

Takahashi can choose at most two of these squares that are painted white, and paint them black.
Determine if it is possible to make the grid contain 6 or more consecutive squares painted black aligned either vertically, horizontally, or diagonally.
Here, the grid is said to be containing 6 or more consecutive squares painted black aligned diagonally if the grid with N rows and N columns completely contains a subgrid with 6 rows and 6 columns such that all the squares on at least one of its diagonals are painted black.

Constraints

• 6 \leq N \leq 1000
• \lvert S_i\rvert =N
• S_i consists of # and ..

Sample Input 1

8
........
........
.#.##.#.
........
........
........
........
........

Sample Output 1

Yes

By painting the 3-rd and the 6-th squares from the left in the 3-rd row from the top, there will be 6 squares painted black aligned horizontally.

Sample Input 2

6
######
######
######
######
######
######

Sample Output 2

Yes

While Takahashi cannot choose a square to paint black, the grid already satisfies the condition.

Sample Input 3

10
..........
#..##.....
..........
..........
....#.....
....#.....
.#...#..#.
..........
..........
..........

Sample Output 3

No

Problem Statement

For two strings A and B, let A+B denote the concatenation of A and B in this order.

You are given N strings S_1,\ldots,S_N. Modify and print them as follows, in the order i=1, \ldots, N:

• if none of S_1,\ldots,S_{i-1} is equal to S_i, print S_i;
• if X (X>0) of S_1,\ldots,S_{i-1} are equal to S_i, print S_i+ ( +X+ ), treating X as a string.

Constraints

• 1 \leq N \leq 2\times 10^5
• S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.

Sample Input 1

5
newfile
newfile
newfolder
newfile
newfolder

Sample Output 1

newfile
newfile(1)
newfolder
newfile(2)
newfolder(1)

Sample Input 2

11
a
a
a
a
a
a
a
a
a
a
a

Sample Output 2

a
a(1)
a(2)
a(3)
a(4)
a(5)
a(6)
a(7)
a(8)
a(9)
a(10)

Problem Statement

Takahashi has N cards in his hand. For i = 1, 2, \ldots, N, the i-th card has an non-negative integer A_i written on it.

First, Takahashi will freely choose a card from his hand and put it on a table. Then, he will repeat the following operation as many times as he wants (possibly zero).

• Let X be the integer written on the last card put on the table. If his hand contains cards with the integer X or the integer (X+1)\bmod M written on them, freely choose one of those cards and put it on the table. Here, (X+1)\bmod M denotes the remainder when (X+1) is divided by M.

Print the smallest possible sum of the integers written on the cards that end up remaining in his hand.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq M \leq 10^9
• 0 \leq A_i \lt M
• All values in the input are integers.

Sample Input 1

9 7
3 0 2 5 5 3 0 6 3

Sample Output 1

11

Assume that he first puts the fourth card (5 is written) on the table and then performs the following.

• Put the fifth card (5 is written) on the table.
• Put the eighth card (6 is written) on the table.
• Put the second card (0 is written) on the table.
• Put the seventh card (0 is written) on the table.

Then, the first, third, sixth, and ninth cards will end up remaining in his hand, and the sum of the integers on those cards is 3 + 2 + 3 +3 = 11. This is the minimum possible sum of the integers written on the cards that end up remaining in his hand.

Sample Input 2

1 10
4

Sample Output 2

0

Sample Input 3

20 20
18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

Sample Output 3

99

Problem Statement

There is an integer sequence A=(A_1,A_2,\ldots,A_N) of length N, where all elements are initially set to 0. Also, there is a set S, which is initially empty.

Perform the following Q queries in order. Find the value of each element in the sequence A after processing all Q queries. The i-th query is in the following format:

• An integer x_i is given. If the integer x_i is contained in S, remove x_i from S. Otherwise, insert x_i to S. Then, for each j=1,2,\ldots,N, add |S| to A_j if j\in S.

Here, |S| denotes the number of elements in the set S. For example, if S=\lbrace 3,4,7\rbrace, then |S|=3.

Constraints

• 1\leq N,Q\leq 2\times10^5
• 1\leq x_i\leq N
• All given numbers are integers.

Sample Input 1

3 4
1 3 3 2

Sample Output 1

6 2 2

In the first query, 1 is inserted to S, making S=\lbrace 1\rbrace. Then, |S|=1 is added to A_1. The sequence becomes A=(1,0,0).

In the second query, 3 is inserted to S, making S=\lbrace 1,3\rbrace. Then, |S|=2 is added to A_1 and A_3. The sequence becomes A=(3,0,2).

In the third query, 3 is removed from S, making S=\lbrace 1\rbrace. Then, |S|=1 is added to A_1. The sequence becomes A=(4,0,2).

In the fourth query, 2 is inserted to S, making S=\lbrace 1,2\rbrace. Then, |S|=2 is added to A_1 and A_2. The sequence becomes A=(6,2,2).

Eventually, the sequence becomes A=(6,2,2).

Sample Input 2

4 6
1 2 3 2 4 2

Sample Output 2

15 9 12 7

Problem Statement

You are given a string S of length N consisting of lowercase English letters.
Process Q queries described below in the order they are given.
There are two types of queries:

• 1 x c : Change the x-th character of S to the lowercase English letter c.
• 2 L R : If the substring formed by the L-th through R-th characters of S is a palindrome, print Yes; otherwise, print No.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq Q \leq 10^5
• S is a string of length N consisting of lowercase English letters.
• 1 \leq x \leq N
• c is a lowercase English letter.
• 1 \leq L \leq R \leq N
• N, Q, x, L, R are integers.

Sample Input 1

7 8
abcbacb
2 1 5
2 4 7
2 2 2
1 5 c
2 1 5
2 4 7
1 4 c
2 3 6

Sample Output 1

Yes
No
Yes
No
Yes
Yes

Initially, S = abcbacb.
For the first query, the string formed by the 1-st through 5-th characters of S is abcba, which is a palindrome. Thus, print Yes.
For the second query, the string formed by the 4-th through 7-th character of S is bacb, which is not a palindrome. Thus, print No.
For the third query, the string formed by the 2-nd through 2-nd character of S is b, which is a palindrome. Thus, output Yes.
For the fourth query, change the 5-th character of S to c. S becomes abcbccb.
For the fifth query, the string formed by the 1-st through 5-th character of S is abcbc, which is not a palindrome. Thus, output No.
For the sixth query, the string formed by the 4-th through 7-th character of S is bccb, which is a palindrome. Thus, output Yes.
For the seventh query, change the 4-th character of S to c. S becomes abccccb.
For the eighth query, the string formed by the 3-rd through 6-th character of cccc, which is a palindrome. Thus, output Yes.