Problem Statement

Takahashi is in charge of a stamp rally at a cultural festival. Visitors are given a sheet with an H \times W grid. The rows of the sheet are numbered 1 to H from top to bottom, and the columns are numbered 1 to W from left to right. Initially, all cells on the sheet are . (blank).

The stamp used in the stamp rally is represented by an R \times C grid. Each cell of the stamp is either # (inked part) or . (non-inked part). The rows of the stamp are numbered 1 to R from top to bottom, and the columns are numbered 1 to C from left to right. The i-th row of the stamp is represented by the string S_i.

Takahashi stamps a visitor's sheet a total of N times using the same stamp. The j-th stamping (1 \leq j \leq N) is specified by a pair of integers (r_j, c_j). Here, r_j and c_j can be any integers, including values that are 0 or less, or values that exceed the size of the sheet.

The meaning of (r_j, c_j) is as follows: the stamp is placed so that row 1, column 1 (the top-left corner) of the stamp corresponds to row r_j, column c_j of the sheet. That is, row a, column b of the stamp (1 \leq a \leq R, 1 \leq b \leq C) corresponds to row (r_j + a - 1), column (c_j + b - 1) of the sheet.

When the stamp is pressed, the following processing is performed for each cell (row a, column b) of the stamp:

• If the corresponding position on the sheet (r_j + a - 1,\; c_j + b - 1) is outside the sheet, i.e., r_j + a - 1 < 1 or r_j + a - 1 > H or c_j + b - 1 < 1 or c_j + b - 1 > W, that cell is ignored.
• If the corresponding position on the sheet is within bounds and the stamp cell is #, the corresponding cell on the sheet is changed to # (if it is already #, it remains unchanged).
• If the corresponding position on the sheet is within bounds and the stamp cell is ., no change is made to the corresponding cell on the sheet.

Output the final state of the sheet after all N stampings have been performed.

Constraints

• 1 \leq H \leq 1000
• 1 \leq W \leq 1000
• 1 \leq R \leq 100
• 1 \leq C \leq 100
• S_i is a string of length C consisting of # and . (1 \leq i \leq R)
• 1 \leq N \leq 1000
• -10^4 \leq r_j \leq 10^4 (1 \leq j \leq N)
• -10^4 \leq c_j \leq 10^4 (1 \leq j \leq N)
• All given values are integers (except for strings)

Sample Input 1

5 5
2 2
#.
.#
2
1 1
3 3

Sample Output 1

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

Sample Input 2

7 7
3 3
.#.
###
.#.
3
1 1
5 5
0 -1

Sample Output 2

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

Sample Input 3

10 10
4 4
.##.
####
####
.##.
4
-1 -1
2 7
8 3
1 1

Sample Output 3

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

Problem Statement

A final exam was held in Takahashi's class. N students participated in this exam, and a total of M problems were given.

The j-th problem (1 \leq j \leq M) has a score of P_j. Each student's total score is the sum of the scores of the problems that the student answered correctly (scores of incorrectly answered problems are not added).

The answer result of the i-th student (1 \leq i \leq N) is represented by a string S_i. S_i is a string of length M, where the j-th character being o means the student answered the j-th problem correctly, and x means the student answered it incorrectly.

Determine the rank of each student based on their total scores. The rank of a student is defined as "the number of students whose total score is strictly higher than that student's + 1". Therefore, students with the same total score will have the same rank.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• N \times M \leq 5 \times 10^6
• 1 \leq P_j \leq 1000 (1 \leq j \leq M)
• S_i is a string of length M consisting only of o and x (1 \leq i \leq N)
• N, M, P_j are all integers

Sample Input 1

5 3
100 200 300
oxo
ooo
xxo
oox
xxx

Sample Output 1

2
1
3
3
5

Sample Input 2

4 4
10 20 30 40
ooxx
xxoo
oxox
xoxo

Sample Output 2

4
1
3
2

Sample Input 3

10 5
50 30 20 80 10
ooooo
oxxxx
xoxox
ooxoo
xxxxx
oxoxo
oooox
xxoox
xooox
oxxxo

Sample Output 3

1
9
5
3
10
7
2
6
4
8

Sample Input 4

20 8
15 25 35 45 55 65 75 85
oooooooo
xxxxxxxx
oxoxoxox
xoxoxoxo
ooooxxxx
xxxxoooo
oxxooxxo
xooxxoox
ooxxooxx
xxooxxoo
oxooxoxo
xoxxoxox
oxxxoooo
xoooxoox
oxooxxox
xoxxoxxo
oooxoxox
xxxoxxoo
oxoxooxx
xoxooxoo

Sample Output 4

1
20
13
8
19
4
11
11
17
7
5
18
2
5
14
16
9
9
14
3

Sample Input 5

1 1
1000
o

Sample Output 5

1

Problem Statement

Takahashi is participating in an N-day reading challenge. On day i (1 \leq i \leq N), he plans to read A_i pages. Takahashi's reading speed is constant, taking C minutes to read one page.

In this challenge, he can select a period of K or more consecutive days and report it as a "reading period." Specifically, he chooses a pair of integers (l, r) satisfying 1 \leq l \leq r \leq N and r - l + 1 \geq K, and designates the days from day l to day r as the reading period. However, a reading period can only be reported if the total reading time during that period is at most the time limit of T minutes. The total reading time from day l to day r is C \times (A_l + A_{l+1} + \cdots + A_r) minutes.

Find the number of reading periods that can be reported. That is, find the number of pairs of integers (l, r) that satisfy both of the following conditions:

• 1 \leq l \leq r \leq N and r - l + 1 \geq K
• C \times (A_l + A_{l+1} + \cdots + A_r) \leq T

Constraints

• 1 \leq N \leq 2 \times 10^6
• 1 \leq C \leq 10^9
• 1 \leq T \leq 10^{18}
• 1 \leq K \leq N
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

5 2 20 2
3 4 5 2 1

Sample Output 1

5

Sample Input 2

4 10 50 2
3 4 2 5

Sample Output 2

0

Sample Input 3

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

Sample Output 3

7

Sample Input 4

50 7 1000 5
12 25 7 30 18 22 15 9 40 11 13 27 5 34 20 16 8 29 24 6 10 31 19 14 28 17 21 4 35 23 26 12 9 33 7 18 25 11 30 6 15 22 13 27 5 20 16 8 24 10

Sample Output 4

147

Sample Input 5

1 1000000000 1000000000000000000 1
1000000000

Sample Output 5

1

Problem Statement

Takahashi is trying to build N block towers lined up in a row from left to right. The target height of the i-th block tower is H_i blocks.

The construction proceeds in steps, where one block is stacked in each step. In each step, Takahashi chooses one block tower that has not yet reached its target height, and places one block on top of it (increasing its height by 1). Initially, all block towers have a height of 0. The construction is complete when all block towers have reached their target heights.

To make the exhibition look good, Takahashi must always satisfy the following condition:

Appearance Condition: Immediately after each step, when looking at the row of block towers from the left end, the "number of visible towers" must be at least K.

When looking at the row of block towers from the left end, the i-th tower is "visible" if its current height is at least 1, and it is strictly greater than the current heights of all towers to its left. For i = 1, it is visible if its height is at least 1.

More precisely, letting h_1, h_2, \ldots, h_N be the current heights of the towers, tower i is visible if h_i \geq 1 and h_i > \max(h_1, h_2, \ldots, h_{i-1}) (for i = 1, it is visible if h_1 \geq 1).

Takahashi wants to determine whether it is possible to complete the construction while satisfying this appearance condition. Furthermore, if it is possible, he wants to find the number of valid construction procedures (sequences of steps).

If it is possible to stack all block towers to their target heights while satisfying the condition, output the total number of such construction procedures modulo 10^9 + 7. If it is impossible, output 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N
• 1 \leq H_i \leq 10^6
• \sum_{i=1}^{N} H_i \leq 10^6
• All input values are integers.

Sample Input 1

3 1
1 2 1

Sample Output 1

12

Sample Input 2

4 2
1 1 1 1

Sample Output 2

0

Sample Input 3

8 1
3 1 4 2 5 2 1 3

Sample Output 3

821889649

Sample Input 4

20 1
12 7 25 18 3 30 11 6 22 14 9 27 5 16 20 8 24 13 10 19

Sample Output 4

85505878

Sample Input 5

1 1
1

Sample Output 5

1

Problem Statement

Takahashi works as a delivery driver. Today, he has a job to deliver packages to multiple destinations.

In Takahashi's service area, there are N locations, numbered 1 to N. There are M bidirectional roads connecting these locations. The i-th road connects location U_i and location V_i, and the travel time is W_i.

Takahashi must start from the office at location 1 and eventually arrive at the warehouse at location N. Along the way, he must visit all of the K designated delivery destinations to deliver the packages. These destinations are given as C_1, C_2, \dots, C_K. The order in which he visits these destinations is arbitrary.

Takahashi wants to finish the deliveries as quickly as possible. Find the minimum total travel time to start from location 1, visit all K destinations, and finally arrive at location N.

Note that he can pass through locations other than the destinations, and he is allowed to visit the same location or road multiple times. It is guaranteed that it is possible to visit all destinations and arrive at location N.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 5 \times 10^4
• 1 \leq K \leq 15
• 1 \leq U_i, V_i \leq N
• U_i \neq V_i
• 1 \leq W_i \leq 10^9
• 1 \leq C_j \leq N
• C_j are all distinct
• C_j \neq 1 and C_j \neq N
• It is guaranteed that it is possible to visit all destinations and arrive at location N.
• All input values are integers

Sample Input 1

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

Sample Output 1

7

Sample Input 2

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

Sample Output 2

12

Sample Input 3

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

Sample Output 3

24

Sample Input 4

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

Sample Output 4

82

Sample Input 5

3 2 1
1 2 1000000000
2 3 1000000000
2

Sample Output 5

2000000000