Problem Statement

There is an enemy with stamina A. Every time you attack the enemy, its stamina reduces by B.

At least how many times do you need to attack the enemy to make its stamina 0 or less?

Constraints

• 1 \le A,B \le 10^{18}
• A and B are integers.

Sample Input 1

7 3

Sample Output 1

3

Attacking three times make the enemy's stamina -2.

Attacking only twice makes the stamina 1, so you need to attack it three times.

Sample Input 2

123456789123456789 987654321

Sample Output 2

124999999

Sample Input 3

999999999999999998 2

Sample Output 3

499999999999999999

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Each cell has a lowercase English letter written on it. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left.

The letters written on the grid are represented by H strings S_1,S_2,\ldots, S_H, each of length W. The j-th letter of S_i represents the letter written on (i, j).

There is a unique set of contiguous cells (going vertically, horizontally, or diagonally) in the grid with s, n, u, k, and e written on them in this order.
Find the positions of such cells and print them in the format specified in the Output section.

A tuple of five cells (A_1,A_2,A_3,A_4,A_5) is said to form a set of contiguous cells (going vertically, horizontally, or diagonally) with s, n, u, k, and e written on them in this order if and only if all of the following conditions are satisfied.

• A_1,A_2,A_3,A_4 and A_5 have letters s, n, u, k, and e written on them, respectively.
• For all 1\leq i\leq 4, cells A_i and A_{i+1} share a corner or a side.
• The centers of A_1,A_2,A_3,A_4, and A_5 are on a common line at regular intervals.

Constraints

• 5\leq H\leq 100
• 5\leq W\leq 100
• H and W are integers.
• S_i is a string of length W consisting of lowercase English letters.
• The given grid has a unique conforming set of cells.

Sample Input 1

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

Sample Output 1

5 2
5 3
5 4
5 5
5 6

Tuple (A_1,A_2,A_3,A_4,A_5)=((5,2),(5,3),(5,4),(5,5),(5,6)) satisfies the conditions.
Indeed, the letters written on them are s, n, u, k, and e;
for all 1\leq i\leq 4, cells A_i and A_{i+1} share a side;
and the centers of the cells are on a common line.

Sample Input 2

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

Sample Output 2

5 5
4 4
3 3
2 2
1 1

Tuple (A_1,A_2,A_3,A_4,A_5)=((5,5),(4,4),(3,3),(2,2),(1,1)) satisfies the conditions.
However, for example, (A_1,A_2,A_3,A_4,A_5)=((3,5),(4,4),(3,3),(2,2),(3,1)) violates the third condition because the centers of the cells are not on a common line, although it satisfies the first and second conditions.

Sample Input 3

10 10
kseeusenuk
usesenesnn
kskekeeses
nesnusnkkn
snenuuenke
kukknkeuss
neunnennue
sknuessuku
nksneekknk
neeeuknenk

Sample Output 3

9 3
8 3
7 3
6 3
5 3

Problem Statement

You are given N strings S_1,S_2,\dots,S_N, each of length M, consisting of lowercase English letter. Here, S_i are pairwise distinct.

Determine if one can rearrange these strings to obtain a new sequence of strings T_1,T_2,\dots,T_N such that:

• for all integers i such that 1 \le i \le N-1, one can alter exactly one character of T_i to another lowercase English letter to make it equal to T_{i+1}.

Constraints

• 2 \le N \le 8
• 1 \le M \le 5
• S_i is a string of length M consisting of lowercase English letters. (1 \le i \le N)
• S_i are pairwise distinct.

Sample Input 1

4 4
bbed
abcd
abed
fbed

Sample Output 1

Yes

One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.

Sample Input 2

2 5
abcde
abced

Sample Output 2

No

No matter how the strings are rearranged, the condition is never satisfied.

Sample Input 3

8 4
fast
face
cast
race
fact
rice
nice
case

Sample Output 3

Yes

Problem Statement

Takahashi has decided to give one gift to Aoki and one gift to Snuke.
There are N candidates of gifts for Aoki, and their values are A_1, A_2, \ldots,A_N.
There are M candidates of gifts for Snuke, and their values are B_1, B_2, \ldots,B_M.

Takahashi wants to choose gifts so that the difference in values of the two gifts is at most D.

Determine if he can choose such a pair of gifts. If he can, print the maximum sum of values of the chosen gifts.

Constraints

• 1\leq N,M\leq 2\times 10^5
• 1\leq A_i,B_i\leq 10^{18}
• 0\leq D \leq 10^{18}
• All values in the input are integers.

Sample Input 1

2 3 2
3 10
2 5 15

Sample Output 1

8

The difference of values of the two gifts should be at most 2.
If he gives a gift with value 3 to Aoki and another with value 5 to Snuke, the condition is satisfied, achieving the maximum possible sum of values.
Thus, 3+5=8 should be printed.

Sample Input 2

3 3 0
1 3 3
6 2 7

Sample Output 2

-1

He cannot choose gifts to satisfy the condition. Note that the candidates of gifts for a person may contain multiple gifts with the same value.

Sample Input 3

1 1 1000000000000000000
1000000000000000000
1000000000000000000

Sample Output 3

2000000000000000000

Note that the answer may not fit into a 32-bit integer type.

Sample Input 4

8 6 1
2 5 6 5 2 1 7 9
7 2 5 5 2 4

Sample Output 4

14

Problem Statement

There is an undirected graph with N vertices numbered 1 through N, and initially with 0 edges.
Given Q queries, process them in order. After processing each query, print the number of vertices that are not connected to any other vertices by an edge.

The i-th query, \mathrm{query}_i, is of one of the following two kinds.

• 1 u v: connect vertex u and vertex v with an edge. It is guaranteed that, when this query is given, vertex u and vertex v are not connected by an edge.

• 2 v: remove all edges that connect vertex v and the other vertices. (Vertex v itself is not removed.)

Constraints

• 2 \leq N\leq 3\times 10^5
• 1 \leq Q\leq 3\times 10^5
• For each query of the first kind, 1\leq u,v\leq N and u\neq v.
• For each query of the second kind, 1\leq v\leq N.
• Right before a query of the first kind is given, there is no edge between vertices u and v.
• All values in the input are integers.

Sample Input 1

3 7
1 1 2
1 1 3
1 2 3
2 1
1 1 2
2 2
1 1 2

Sample Output 1

1
0
0
1
0
3
1

After the first query, vertex 1 and vertex 2 are connected to each other by an edge, but vertex 3 is not connected to any other vertices.
Thus, 1 should be printed in the first line.

After the third query, all pairs of different vertices are connected by an edge.
However, the fourth query asks to remove all edges that connect vertex 1 and the other vertices, specifically to remove the edge between vertex 1 and vertex 2, and another between vertex 1 and vertex 3. As a result, vertex 2 and vertex 3 are connected to each other, while vertex 1 is not connected to any other vertices by an edge.
Thus, 0 and 1 should be printed in the third and fourth lines, respectively.

Sample Input 2

2 1
2 1

Sample Output 2

2

When the query of the second kind is given, there may be no edge that connects that vertex and the other vertices.

Problem Statement

On a blackboard, there are N sets S_1,S_2,\dots,S_N consisting of integers between 1 and M. Here, S_i = \lbrace S_{i,1},S_{i,2},\dots,S_{i,A_i} \rbrace.

You may perform the following operation any number of times (possibly zero):

• choose two sets X and Y with at least one common element. Erase them from the blackboard, and write X\cup Y on the blackboard instead.

Here, X\cup Y denotes the set consisting of the elements contained in at least one of X and Y.

Determine if one can obtain a set containing both 1 and M. If it is possible, find the minimum number of operations required to obtain it.

Constraints

• 1 \le N \le 2 \times 10^5
• 2 \le M \le 2 \times 10^5
• 1 \le \sum_{i=1}^{N} A_i \le 5 \times 10^5
• 1 \le S_{i,j} \le M(1 \le i \le N,1 \le j \le A_i)
• S_{i,j} \neq S_{i,k}(1 \le j < k \le A_i)
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

2

First, choose and remove \lbrace 1,2 \rbrace and \lbrace 2,3 \rbrace to obtain \lbrace 1,2,3 \rbrace.

Then, choose and remove \lbrace 1,2,3 \rbrace and \lbrace 3,4,5 \rbrace to obtain \lbrace 1,2,3,4,5 \rbrace.

Thus, one can obtain a set containing both 1 and M with two operations. Since one cannot achieve the objective by performing the operation only once, the answer is 2.

Sample Input 2

1 2
2
1 2

Sample Output 2

0

S_1 already contains both 1 and M, so the minimum number of operations required is 0.

Sample Input 3

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

Sample Output 3

-1

Sample Input 4

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

Sample Output 4

2

Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N, consisting of integers between 1 and 4.

Takahashi may perform the following operation any number of times (possibly zero):

• choose a pair of integer (i,j) such that 1\leq i<j\leq N, and swap A_i and A_j.

Find the minimum number of operations required to make A non-decreasing.
A sequence is said to be non-decreasing if and only if A_i\leq A_{i+1} for all 1\leq i\leq N-1.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1\leq A_i \leq 4
• All values in the input are integers.

Sample Input 1

6
3 4 1 1 2 4

Sample Output 1

3

One can make A non-decreasing with the following three operations:

• Choose (i,j)=(2,3) to swap A_2 and A_3, making A=(3,1,4,1,2,4).
• Choose (i,j)=(1,4) to swap A_1 and A_4, making A=(1,1,4,3,2,4).
• Choose (i,j)=(3,5) to swap A_3 and A_5, making A=(1,1,2,3,4,4).

This is the minimum number of operations because it is impossible to make A non-decreasing with two or fewer operations.
Thus, 3 should be printed.

Sample Input 2

4
2 3 4 1

Sample Output 2

3

Problem Statement

We have a tree with N vertices. The i-th (1 \le i \le N-1) edge is an undirected edge between vertices U_i and V_i. Vertex i (1 \le i \le N) has a ball with A_i written on it and another with B_i.

For each v = 2,3,\dots,N, answer the following question. (Each query is independent.)

• Consider traveling from vertex 1 to vertex v on the shortest path. Every time you visit a vertex (including vertices 1 and v), you pick up one ball placed there. Find the maximum number of distinct integers written on the picked-up balls.

Constraints

• 2 \le N \le 2 \times 10^5
• 1 \le A_i,B_i \le N
• The given graph is a tree.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

2 3 3

For example, when v=4, you visit vertices 1,2,3, and 4. By choosing balls with A_1,B_2,B_3,B_4(=1,3,1,2) written on them, the number of distinct integers on the balls is 3, which is the maximum.

Sample Input 2

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

Sample Output 2

4 3 2 3 4 3 4 2 3