Problem Statement

Takahashi is a network administrator at a company. He is conducting a security assessment of the company's internal network.

The internal network consists of server rooms arranged in a grid of N rows and M columns. Each room either contains a server or is empty. A room with a server is represented by #, and an empty room is represented by ..

For each room containing a server, the number of adjacent rooms (up, down, left, right) within the grid that also contain servers is called the "adjacent server count". Since no rooms exist outside the grid, rooms outside the grid are not considered when counting adjacent servers.

A server with an adjacent server count of 0 is isolated and lacks redundancy in case of failure, while a server with an adjacent server count of 4 has too much load concentrated on it. Both cases are considered security risks. Therefore, the security policy defines the following condition:

• For every server, the adjacent server count must be at least 1 and at most 3.

Takahashi has been given the current network layout and must determine whether this layout satisfies the security policy.

Determine whether the given network layout satisfies the security policy condition. Note that if no servers are installed at all, there are no servers violating the condition, so the security policy is considered satisfied.

Constraints

• 1 \leq N \leq 1000
• 1 \leq M \leq 1000
• S_i (1 \leq i \leq N) is a string of length M consisting only of # and .

Sample Input 1

3 3
.#.
###
.#.

Sample Output 1

No

Sample Input 2

4 5
.....
.#.#.
.###.
.....

Sample Output 2

Yes

Sample Input 3

5 8
........
.##.###.
.##.#.#.
....###.
........

Sample Output 3

Yes

Problem Statement

Takahashi is trying to buy N items at a supermarket. The regular price of the j-th item is C_j yen. Takahashi must purchase all N items.

This supermarket offers a tiered discount service based on the total amount in a single checkout. There are K tiers, numbered from 1 to K. Each tier i has a minimum threshold amount T_i yen and a discount rate P_i%. The tier thresholds satisfy T_1 < T_2 < \cdots < T_K, and in particular T_1 = 0. The discount rates satisfy P_1 \leq P_2 \leq \cdots \leq P_K.

Let X yen be the total amount at checkout. The tier applied to X is the largest i such that T_i \leq X. The discount rate P_i% of that tier is applied, and the discount amount is \lfloor X \times P_i / 100 \rfloor yen (rounded down). Therefore, the payment at the supermarket is X - \lfloor X \times P_i / 100 \rfloor yen.

Takahashi will check out at this supermarket exactly once. Before going to the register, he can return any items from his cart to the shelves. Items returned to the shelves will be purchased at another store at their regular price (without any discount).

Specifically, Takahashi selects a subset A (possibly empty) of the N items to bring to the supermarket register. Let X be the sum of the regular prices of the items in A. The total amount Takahashi pays is the sum of:

• Payment at the supermarket: X - \lfloor X \times P_i / 100 \rfloor yen (applying the discount rate P_i of the tier i corresponding to X)
• Payment at the other store: the sum of the regular prices of the items not in A

Find the minimum total amount Takahashi pays when he optimally chooses the subset A.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 2 \times 10^5
• 0 = T_1 < T_2 < \cdots < T_K \leq 2 \times 10^{14}
• 0 \leq P_1 \leq P_2 \leq \cdots \leq P_K \leq 100
• 1 \leq C_j \leq 10^9 (1 \leq j \leq N)
• All inputs are integers

Sample Input 1

3 3
0 0 10 10 20 20
6 8 15

Sample Output 1

24

Sample Input 2

4 4
0 0 30 10 60 10 61 50
10 20 31 5

Sample Output 2

33

Sample Input 3

7 5
0 0 50 5 120 12 200 20 350 25
17 33 45 60 88 120 150

Sample Output 3

385

Sample Input 4

12 8
0 0 500000000 2 1000000000 3 2000000000 5 3000000000 7 4000000000 10 5500000000 15 200000000000000 17
999999999 850000000 760000000 640000000 530000000 470000000 390000000 310000000 280000000 220000000 150000000 90000000

Sample Output 4

4836500000

Sample Input 5

1 1
0 100
1000000000

Sample Output 5

0

Problem Statement

On a number line, Takahashi and Aoki are playing a game of chase. Aoki runs in the positive direction, and Takahashi chases after him.

Their speeds change with a period of N seconds. Initially, a speed table of length N is given, where the i-th entry (1 \leq i \leq N) specifies Aoki's speed A_i and Takahashi's speed B_i.

Time starts from 0. For each non-negative integer s, during the 1-second interval from time s to time s + 1, the i = (s \bmod N) + 1-th entry of the speed table is used. That is, during this 1 second, Aoki moves A_i and Takahashi moves B_i in the positive direction. This correspondence repeats in the same order every N seconds.

You process Q queries in order. There are two types of queries:

• 1 i a b: Change the i-th entry of the speed table so that Aoki's speed becomes a and Takahashi's speed becomes b.
• 2 d: Based on the current speed table, answer the following question. Assuming that at time 0, Takahashi is at coordinate 0 and Aoki is at coordinate d, find the minimum non-negative integer time at which Takahashi catches up to Aoki. If he can never catch up, output -1.

Here, catching up means that at some non-negative integer time t, Takahashi's coordinate is greater than or equal to Aoki's coordinate. The check is performed only at integer times; the positions of the two in between are not considered.

Each 2 query is independent, and the positions of the two are not carried over to the next query. On the other hand, changes to the speed table made by 1 queries are carried over to all subsequent queries.

Constraints

• 1 \leq N \leq 3000
• 1 \leq Q \leq 10^5
• NQ \leq 10^7
• 0 \leq A_i \leq 10^9
• 0 \leq B_i \leq 10^9
• For 1 queries: 1 \leq i \leq N, 0 \leq a \leq 10^9, 0 \leq b \leq 10^9
• For 2 queries: 1 \leq d \leq 10^{15}
• There is at least one 2 query
• All input values are integers

Sample Input 1

3 5
2 5
4 3
1 2
2 1
2 4
1 2 0 6
2 8
2 20

Sample Output 1

1
4
2
6

Sample Input 2

3 5
2 1
0 2
1 0
2 2
2 1
1 2 5 5
2 1
2 100

Sample Output 2

-1
2
-1
-1

Sample Input 3

8 14
5 8
7 4
3 6
10 2
0 5
4 4
6 9
2 1
2 3
2 10
1 4 1 12
2 15
1 8 5 20
2 30
1 2 10 10
2 7
2 100
1 5 8 0
2 12
1 4 0 0
2 25
2 1

Sample Output 3

1
33
5
8
4
21
4
16
1

Sample Input 4

20 30
100 150
80 60
0 200
300 100
50 50
20 70
90 30
10 110
400 0
0 0
15 45
60 90
120 80
5 205
700 900
1000 500
30 31
45 40
200 250
75 125
2 1000
2 100000
1 9 0 1000
2 5000
1 16 100 1000
2 20000
1 4 0 0
1 7 0 300
2 12345
2 999999999999999
1 1 1000 0
2 100
1 10 0 1000000000
2 1000000000
1 10 1000000000 0
2 1000000000
1 15 900 700
1 20 125 75
2 7777
2 42
1 2 0 0
1 3 500 100
2 314159
1 18 0 100
2 271828
1 5 0 0
2 1000000000000000
1 12 1000000000 1000000000
2 600
2 600000

Sample Output 4

-1
-1
89
156
80
6459948320415
9
10
-1
-1
9
-1
-1
-1
-1
-1

Sample Input 5

1 8
1000000000 0
2 1
1 1 0 0
2 1
1 1 0 1000000000
2 1000000000000000
2 1
1 1 1000000000 1000000000
2 1

Sample Output 5

-1
-1
1000000
1
-1

Problem Statement

Takahashi is the group leader for a school trip. The group has N members including Takahashi, and Takahashi purchased M types of sweets at a souvenir shop. There are C_i pieces of the i-th type of sweet.

Takahashi wants to distribute these sweets to all members of the group (N people including himself). The rules for distribution are as follows:

• Each member receives exactly K sweets.
• Each individual sweet can be given to only one member. That is, at most C_i pieces of the i-th type of sweet can be distributed in total.
• No member may receive 2 or more sweets of the same type. That is, the K sweets each member receives must all be of different types. However, different members are allowed to each receive sweets of the same type.
• It is acceptable to have leftover sweets.

Determine whether it is possible to distribute exactly K sweets to every member. If it is possible, output Yes; otherwise, output No.

Constraints

• 1 \leq N \leq 10^9
• 1 \leq M \leq 2 \times 10^5
• 1 \leq K \leq M
• 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
• All input values are integers.

Sample Input 1

3 4 2
3 3 3 3

Sample Output 1

Yes

Sample Input 2

5 3 3
2 2 2

Sample Output 2

No

Sample Input 3

1000000000 5 3
1000000000 1000000000 500000000 500000000 999999999

Sample Output 3

Yes

Problem Statement

In this problem, a convex figure refers to one of the following:

• Point: A set consisting of a single point on the plane.
• Line segment: A line segment connecting two distinct points on the plane (the set consisting of both endpoints and all interior points).
• Convex polygon: A convex polygon with 3 or more vertices where not all vertices are collinear (the set consisting of all vertices, points on edges, and interior points). In this case, the area is positive.

Takahashi has N convex figures. The i-th convex figure P_i is represented by K_i vertices, following these rules:

• If K_i = 1, then P_i is the point (x_{i,1}, y_{i,1}).
• If K_i = 2, then P_i is the line segment connecting the two points (x_{i,1}, y_{i,1}) and (x_{i,2}, y_{i,2}).
• If K_i \geq 3 and not all K_i vertices are collinear, then P_i is the convex polygon with those vertices. If K_i \geq 3 and all K_i vertices are collinear, then P_i is the shortest line segment containing all of them (i.e., the convex hull of all vertices).

The Minkowski sum A \oplus B of two convex figures A, B is defined as follows:

A \oplus B = \{ \mathbf{a} + \mathbf{b} \mid \mathbf{a} \in A,\ \mathbf{b} \in B \}

Here, \mathbf{a} + \mathbf{b} denotes the coordinate-wise sum. It is known that the Minkowski sum of two convex figures is again a convex figure.

Consider ways to select one or more of the N convex figures. Each convex figure can be selected at most once. That is, we choose a non-empty subset S \subseteq \{P_1, P_2, \ldots, P_N\}. We write the Minkowski sum of all figures in S as

\bigoplus_{P \in S} P

If S consists of exactly one figure, this value is that figure itself. Since the Minkowski sum is associative and commutative, the result is uniquely determined regardless of the order in which the binary operation is applied.

There are 2^N - 1 ways to choose a non-empty subset S. Among these, find the number of subsets for which \bigoplus_{P \in S} P is a convex polygon (i.e., not a point or a line segment, but a convex polygon with positive area), modulo 10^9 + 7.

Constraints

• 1 \leq N \leq 5 \times 10^4
• 1 \leq K_i \leq 50
• \sum_{i=1}^{N} K_i \leq 10^5
• |x_{i,j}| \leq 10^9,\ |y_{i,j}| \leq 10^9
• For each convex figure, the given K_i vertices are all distinct.
• If K_i \geq 3 and not all vertices are collinear, the vertices are given in counterclockwise order, and no three cyclically consecutive vertices are collinear (i.e., there are no vertices with interior angle 0° or 180°).
• If K_i \geq 3 and all vertices are collinear, the vertices are ordered from one endpoint of the line segment containing all vertices to the other endpoint (i.e., the first and last vertices are the two endpoints of this line segment).
• All input values are integers.

Sample Input 1

3
1
0 0
2
1 0
1 2
3
0 0
2 0
0 2

Sample Output 1

4

Sample Input 2

3
1
2 3
3
0 0
2 0
5 0
2
-1 0
4 0

Sample Output 2

0

Sample Input 3

6
1
1 -1
2
0 0
2 1
3
-2 -1
0 -1
3 -1
4
-1 0
2 0
2 2
-1 2
5
0 0
2 -1
4 0
3 2
1 2
2
-3 1
-1 4

Sample Output 3

56

Sample Input 4

10
1
0 0
1
5 -3
2
0 0
2 0
4
-3 -3
-1 -1
1 1
4 4
3
0 0
3 0
1 2
4
-2 1
2 1
2 4
-2 4
5
-3 0
-1 -2
2 -1
3 2
0 3
3
-5 -1
-3 -4
-1 -2
3
7 -1
7 0
7 3
6
0 0
2 -1
4 0
5 2
3 4
1 3

Sample Output 4

1008

Sample Input 5

1
50
0 1
1 3
2 5
3 7
4 9
5 11
6 13
7 15
8 17
9 19
10 21
11 23
12 25
13 27
14 29
15 31
16 33
17 35
18 37
19 39
20 41
21 43
22 45
23 47
24 49
25 51
26 53
27 55
28 57
29 59
30 61
31 63
32 65
33 67
34 69
35 71
36 73
37 75
38 77
39 79
40 81
41 83
42 85
43 87
44 89
45 91
46 93
47 95
48 97
49 99

Sample Output 5

0