Problem Statement

Takahashi is a member of the astronomy club and is organizing his nighttime sky observation records. The observation data is recorded as a grid image with H rows and W columns, where each cell either contains nothing or contains a star.

Cell positions are represented as (i, j), where (1, 1) is the top-left cell, and (i, j) denotes the cell in the i-th row from the top and the j-th column from the left. The i-th row of the observation data is represented by the string S_i, where if the j-th character of S_i is T, it means a star is captured in cell (i, j), and if it is ., it means nothing is captured there.

Given the observation data, find the positions of all cells that contain stars. Output the stars in ascending order of row number, and for stars in the same row, in ascending order of column number.

Constraints

• 1 \leq H \leq 1000
• 1 \leq W \leq 1000
• H, W are integers
• S_i (1 \leq i \leq H) is a string of length W consisting only of . and T
• It is possible that no T is included (i.e., there are 0 stars)

Sample Input 1

3 5
T..T.
.....
..T..

Sample Output 1

3
1 1
1 4
3 3

Sample Input 2

5 8
........
.T....T.
........
.T..T...
....T..T

Sample Output 2

6
2 2
2 7
4 2
4 5
5 5
5 8

Sample Input 3

10 15
T.............T
...T...........
.......T.......
...............
.T.............
...............
..........T....
...............
.............T.
T..T..T..T..T..

Sample Output 3

12
1 1
1 15
2 4
3 8
5 2
7 11
9 14
10 1
10 4
10 7
10 10
10 13

Problem Statement

Takahashi works in the general affairs department of a company. He needs to organize a meeting that all N employees must attend.

The company has M meeting rooms, numbered from 1 to M.

For each employee i (1 \leq i \leq N), due to scheduling constraints, there is a positive integer P_i representing their participation condition. Employee i can only attend in a meeting room whose number is a multiple of P_i. In other words, employee i can attend in meeting room j if and only if j is a multiple of P_i.

Takahashi wants to find a meeting room that all employees can attend. Specifically, determine whether there exists a meeting room number j (1 \leq j \leq M) such that j is a multiple of P_i for every employee i (1 \leq i \leq N).

If such a meeting room exists, output Yes; otherwise, output No.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^{18}
• 1 \leq P_i \leq 10^9
• All input values are integers.

Sample Input 1

3 12
2 3 4

Sample Output 1

Yes

Sample Input 2

4 100
6 10 15 3

Sample Output 2

Yes

Sample Input 3

5 1000000000000000000
12 18 24 36 48

Sample Output 3

Yes

Sample Input 4

3 50
7 11 13

Sample Output 4

No

Problem Statement

Takahashi is investing in N stocks. The current asset value of stock i (1 \leq i \leq N) is S_i.

Takahashi will now perform the following operation exactly K times.

• Choose one of the N stocks and double its current asset value.

He may freely choose which stock to select for each operation, and the same stock may be chosen multiple times. If the same stock is chosen multiple times, the doubling operation is applied cumulatively each time. For example, if a stock with asset value S is chosen 3 times, its asset value becomes 2^3 \times S = 8S.

Takahashi wants to maximize the total asset value of all N stocks after performing all K operations.

When the choice of stocks for the operations is made optimally, find the maximum possible total asset value of the N stocks after K operations. Since the answer can be very large, output the maximum total modulo 10^9 + 7.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^{18}
• 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

3 2
1 3 2

Sample Output 1

15

Sample Input 2

4 3
5 5 1 2

Sample Output 2

48

Sample Input 3

10 20
12 7 25 3 18 30 1 9 14 22

Sample Output 3

31457391

Sample Input 4

40 123456789012345678
100000000 250000000 333333333 123456789 987654321 456789123 789123456 111111111 222222222 444444444 555555555 666666666 777777777 888888888 999999937 314159265 271828182 161803398 141421356 173205080 999999999 1 2 3 999999998 500000000 600000000 700000000 800000000 900000000 135791357 246802468 102030405 908070605 112233445 556677889 424242424 123123123 321321321 999000999

Sample Output 4

448506850

Sample Input 5

1 1000000000000000000
1000000000

Sample Output 5

963666222

Problem Statement

Takahashi and Aoki play a game using cards.

N cards are arranged in a row on the table, and the i-th card from the left has an integer V_i written on it. Note that V_i may be negative.

The two players take cards according to the following rules:

• Takahashi goes first, Aoki goes second, and they take turns alternately.
• On their turn, a player chooses exactly one card from either the left end or the right end of the row of cards remaining on the table, takes it, and places it in their hand. The taken card is removed from the table, and the order of the remaining cards does not change.
• The game ends when all cards have been taken.

Both players know all information including each other's strategies, and each plays optimally to maximize the sum of the integers written on the cards they have taken.

When both players play optimally, find the value obtained by subtracting the sum of the integers written on the cards Aoki took from the sum of the integers written on the cards Takahashi took.

Constraints

• 1 \leq N \leq 3000
• -10^9 \leq V_i \leq 10^9
• All inputs are integers.

Sample Input 1

4
3 1 2 5

Sample Output 1

3

Sample Input 2

4
-1 5 -3 2

Sample Output 2

11

Sample Input 3

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

Sample Output 3

15

Sample Input 4

20
15 -8 23 4 -12 7 19 -3 11 6 -5 14 2 -9 18 1 -6 10 8 -2

Sample Output 4

53

Sample Input 5

1
-1000000000

Sample Output 5

-1000000000

Problem Statement

Takahashi manages a coloring sheet consisting of N cells arranged in a horizontal row. The cells are numbered from 1 to N from left to right.

Each cell i is painted with color C_i. In a sequence of cells, a maximal consecutive interval of the same color that cannot be extended further is called a block. The number of blocks in an interval [L, R] is the number of blocks when the cell sequence C_L, C_{L+1}, \dots, C_R is divided into blocks.

For example, if the sequence is 1, 1, 2, 2, 2, 1, the blocks are (1, 1), (2, 2, 2), (1), giving 3 blocks, so the number of blocks is 3.

Aoki performs a total of Q operations of the following two types. Process each operation in order and answer the queries.

• 1 L R X: Change the color of all cells in the interval [L, R] to X.
• 2 L R: Output the number of blocks in the current interval [L, R].

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 10^5
• 1 \leq C_i \leq 10^9
• For operation 1 L R X: 1 \leq L \leq R \leq N, 1 \leq X \leq 10^9
• For operation 2 L R: 1 \leq L \leq R \leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
2
1
3

Sample Input 2

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

Sample Output 2

3
1
1
2
1

Sample Input 3

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

Sample Output 3

7
4
4
4
3
1
3

Sample Input 4

20 18
1 1 2 3 3 4 4 4 5 6 6 7 8 8 9 9 9 10 1 1
2 1 20
2 4 17
1 3 8 3
2 1 10
1 10 15 8
2 8 18
1 1 2 2
2 1 5
1 16 20 8
2 10 20
1 5 5 2
2 1 20
1 6 14 1
2 1 20
2 6 14
1 1 20 7
2 1 20
2 11 11

Sample Output 4

11
7
4
5
2
1
6
5
1
1
1

Sample Input 5

1 5
1000000000
2 1 1
1 1 1 1
2 1 1
1 1 1 1000000000
2 1 1

Sample Output 5

1
1
1