Problem Statement

There is an N \times N grid, where the cell at the i-th row from the top and the j-th column from the left contains the integer N \times (i-1) + j.

Over T turns, integers will be announced. On Turn i, the integer A_i is announced, and the cell containing A_i is marked. Determine the turn on which Bingo is achieved for the first time. If Bingo is not achieved within T turns, print -1.

Here, achieving Bingo means satisfying at least one of the following conditions:

• There exists a row in which all N cells are marked.
• There exists a column in which all N cells are marked.
• There exists a diagonal line (from top-left to bottom-right or from top-right to bottom-left) in which all N cells are marked.

Constraints

• 2 \leq N \leq 2 \times 10^3
• 1 \leq T \leq \min(N^2, 2 \times 10^5)
• 1 \leq A_i \leq N^2
• A_i \neq A_j if i \neq j.
• All input values are integers.

Sample Input 1

3 5
5 1 8 9 7

Sample Output 1

4

The state of the grid changes as follows. Bingo is achieved for the first time on Turn 4.

Sample Input 2

3 5
4 2 9 7 5

Sample Output 2

-1

Bingo is not achieved within five turns, so print -1.

Sample Input 3

4 12
13 9 6 5 2 7 16 14 8 3 10 11

Sample Output 3

9

Problem Statement

You are given a string S = S_1S_2\ldots S_N of length N consisting of lowercase English letters.

Additionally, you are given Q queries about the string S. For i = 1, 2, \ldots, Q, the i-th query is represented by two integers l_i, r_i and asks the following.

In the substring S_{l_i}S_{l_i+1}\ldots S_{r_i} of S, which ranges from the l_i-th to the r_i-th character, how many places are there where the same lowercase English letter occurs twice in a row? In other words, how many integers p satisfy l_i \leq p \leq r_i-1 and S_p = S_{p+1}?

Print the answer for each of the Q queries.

Constraints

• N and Q are integers.
• 1 \leq N, Q \leq 3 \times 10^5
• S is a string of length N consisting of lowercase English letters.
• l_i and r_i are integers.
• 1 \leq l_i \leq r_i \leq N

Sample Input 1

11 4
mississippi
3 9
4 10
4 6
7 7

Sample Output 1

2
2
0
0

The answers to the four queries are as follows.

• For the first query, S_3S_4\ldots S_9 = ssissip has two places where the same lowercase English letter occurs twice in a row: S_3S_4 = ss and S_6S_7 = ss.
• For the second query, S_4S_5\ldots S_{10} = sissipp has two places where the same lowercase English letter occurs twice in a row: S_6S_7 = ss and S_9S_{10} = pp.
• For the third query, S_4S_5S_6 = sis has zero places where the same lowercase English letter occurs twice in a row.
• For the fourth query, S_7 = s has zero places where the same lowercase English letter occurs twice in a row.

Sample Input 2

5 1
aaaaa
1 5

Sample Output 2

4

S_1S_2\ldots S_5 = aaaaa has four places where the same lowercase English letter occurs twice in a row: S_1S_2 = aa, S_2S_3 = aa, S_3S_4 = aa, and S_4S_5 = aa.

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges. Each vertex i\,(1\leq i \leq N) has a weight A_i. Each edge j\,(1\leq j \leq M) connects vertices U_j and V_j bidirectionally and has a weight B_j.

The weight of a path in this graph is defined as the sum of the weights of the vertices and edges that appear on the path.

For each i=2,3,\dots,N, solve the following problem:

• Find the minimum weight of a path from vertex 1 to vertex i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq 2 \times 10^5
• 1 \leq U_j < V_j \leq N
• (U_i, V_i) \neq (U_j, V_j) if i \neq j.
• The graph is connected.
• 0 \leq A_i \leq 10^9
• 0 \leq B_j \leq 10^9
• All input values are integers.

Sample Input 1

3 3
1 2 3
1 2 1
1 3 6
2 3 2

Sample Output 1

4 9

Consider the paths from vertex 1 to vertex 2. The weight of the path 1 \to 2 is A_1 + B_1 + A_2 = 1 + 1 + 2 = 4, and the weight of the path 1 \to 3 \to 2 is A_1 + B_2 + A_3 + B_3 + A_2 = 1 + 6 + 3 + 2 + 2 = 14. The minimum weight is 4.

Consider the paths from vertex 1 to vertex 3. The weight of the path 1 \to 3 is A_1 + B_2 + A_3 = 1 + 6 + 3 = 10, and the weight of the path 1 \to 2 \to 3 is A_1 + B_1 + A_2 + B_3 + A_3 = 1 + 1 + 2 + 2 + 3 = 9. The minimum weight is 9.

Sample Input 2

2 1
0 1
1 2 3

Sample Output 2

4

Sample Input 3

5 8
928448202 994752369 906965437 942744902 907560126
2 5 975090662
1 2 908843627
1 5 969061140
3 4 964249326
2 3 957690728
2 4 942986477
4 5 948404113
1 3 988716403

Sample Output 3

2832044198 2824130042 4696218483 2805069468

Note that the answers may not fit in a 32-bit integer.

Problem Statement

There are N 7's drawn in the first quadrant of a plane.

The i-th 7 is a figure composed of a segment connecting (x_i-1,y_i) and (x_i,y_i), and a segment connecting (x_i,y_i-1) and (x_i,y_i).

You can choose zero or more from the N 7's and delete them.

What is the maximum possible number of 7's that are wholly visible from the origin after the optimal deletion?

Here, the i-th 7 is wholly visible from the origin if and only if:

• the interior (excluding borders) of the quadrilateral whose vertices are the origin, (x_i-1,y_i), (x_i,y_i), (x_i,y_i-1) does not intersect with the other 7's.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq x_i,y_i \leq 10^9
• (x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
• All values in input are integers.

Sample Input 1

3
1 1
2 1
1 2

Sample Output 1

2

If the first 7 is deleted, the other two 7's ― the second and third ones ― will be wholly visible from the origin, which is optimal.

If no 7's are deleted, only the first 7 is wholly visible from the origin.

Sample Input 2

10
414598724 87552841
252911401 309688555
623249116 421714323
605059493 227199170
410455266 373748111
861647548 916369023
527772558 682124751
356101507 249887028
292258775 110762985
850583108 796044319

Sample Output 2

10

It is best to keep all 7's.

Problem Statement

Given is an undirected graph with N+1 vertices.
The vertices are called Vertex 0, Vertex 1, \ldots, Vertex N.

For each i=1,2,\ldots,N, the graph has an undirected edge with a weight of A_i connecting Vertex 0 and Vertex i.

Additionally, for each i=1,2,\ldots,N, the graph has an undirected edge with a weight of B_i connecting Vertex i and Vertex i+1. (Here, Vertex N+1 stands for Vertex 1.)

The graph has no edge other than these 2N edges above.

Let us delete some of the edges from this graph so that the graph will be bipartite.
What is the minimum total weight of the edges that have to be deleted?

Constraints

• 3 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• All values in input are integers.

Sample Input 1

5
31 4 159 2 65
5 5 5 5 10

Sample Output 1

16

Deleting the edge connecting Vertices 0,2 (weight: 4), the edge connecting Vertices 0,4 (weight: 2), and the edge connecting Vertices 1,5 (weight: 10) makes the graph bipartite.

Sample Input 2

4
100 100 100 1000000000
1 2 3 4

Sample Output 2

10