Problem Statement

There are N items. You are given strings T and A of length N that represent which items Takahashi and Aoki want, respectively. Let T_i and A_i be the i-th (1\leq i\leq N) characters of T and A, respectively.

Takahashi wants the i-th item when T_i is o, and does not want the i-th item when T_i is x. Similarly, Aoki wants the i-th item when A_i is o, and does not want the i-th item when A_i is x.

Determine whether there exists an item that both of them want.

Constraints

• 1\leq N\leq 100
• N is an integer.
• T and A are strings of length N consisting of o and x.

Sample Input 1

4
oxoo
xoox

Sample Output 1

Yes

The third item is wanted by both of them, so output Yes.

Sample Input 2

5
xxxxx
ooooo

Sample Output 2

No

There is no item that both of them want, so output No.

Sample Input 3

10
xoooxoxxxo
ooxooooxoo

Sample Output 3

Yes

Problem Statement

You are given a sequence of non-negative integers A=(A_1,A_2,\dots,A_N) of length N. Find the maximum non-negative integer x that satisfies the following:

• In A, elements greater than or equal to x appear at least x times (including duplicates).

Constraints

• 1 \leq N \leq 100
• 0 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

3
1 2 1

Sample Output 1

1

In A=(1,2,1):

• Elements greater than or equal to 0 appear 3 times.
• Elements greater than or equal to 1 appear 3 times.
• Elements greater than or equal to 2 appear 1 time.
• Elements greater than or equal to 3 appear 0 times.

The maximum non-negative integer that satisfies the condition is 1.

Sample Input 2

7
1 6 2 10 2 3 2

Sample Output 2

3

Problem Statement

There is a circle with circumference L, and points 1,2,\ldots,N are placed on this circle. For i=1,2,\ldots,N-1, point i+1 is located at a position that is d_i clockwise from point i on the circle.

Find the number of integer triples (a,b,c)\ (1\leq a\lt b\lt c\leq N) that satisfy both of the following conditions:

• The three points a, b, and c are all at different positions.
• The triangle with vertices at the three points a, b, and c is an equilateral triangle.

Constraints

• 3\leq L,N\leq 3\times 10^5
• 0\leq d_i\lt L
• All input values are integers.

Sample Input 1

5 6
4 3 1 2

Sample Output 1

2

The arrangement of the five points is as follows. Two pairs satisfy the conditions: (a,b,c)=(1,2,4),(1,4,5).

Sample Input 2

4 4
1 1 1

Sample Output 2

0

Sample Input 3

10 12
4 4 5 7 1 7 0 8 5

Sample Output 3

13

Problem Statement

You are given a string S=S_1S_2\dots S_N of length N consisting of lowercase English letters. You will perform the following operation on S exactly once:

• Choose a contiguous substring of S with length at least 1 and cyclically shift it to the left by 1. That is, choose integers 1 \leq \ell \leq r \leq N, insert S_\ell to the right of the r-th character of S, and then delete the \ell-th character of S.

Find the lexicographically smallest string among all possible strings that S can become after the operation.

You are given T test cases, so solve each of them.

Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^5
• S is a string of length N consisting of lowercase English letters.
• T and N are integers.
• The sum of N over all test cases in a single input file is at most 10^5.

Sample Input 1

3
7
atcoder
1
x
5
snuke

Sample Output 1

acodert
x
nsuke

• In the first test case, cyclically shifting from the 2nd to the 7th character gives acodert, which is lexicographically smallest.
• In the second test case, no matter how you operate, you get x.
• In the third test case, cyclically shifting from the 1st to the 2nd character gives nsuke, which is lexicographically smallest.

Problem Statement

You are given a tree with N vertices. The vertices are numbered 1,2,\dots,N, and the edges are numbered 1,2,\dots,N-1. Edge j bidirectionally connects vertices u_j and v_j and has weight w_j. Also, vertex i is given an integer x_i. If x_i > 0, then x_i positrons are placed at vertex i. If x_i < 0, then -x_i electrons are placed at vertex i. If x_i=0, then nothing is placed at vertex i. Here, it is guaranteed that \sum_{i=1}^N x_i = 0.

Moving one positron or electron along edge j costs energy w_j. Also, when a positron and an electron are at the same vertex, they annihilate each other in equal numbers.

Find the minimum energy required to annihilate all positrons and electrons.

Constraints

• 2 \leq N \leq 10^5
• |x_i| \leq 10^4
• \sum_{i=1}^N x_i = 0
• 1 \leq u_j < v_j \leq N
• 0 \leq w_j \leq 10^4
• The given graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

9

Initially, x=(x_1,x_2,x_3,x_4)=(-3,+2,+2,-1). By operating as follows, all positrons and electrons can be annihilated with energy 9:

• Move one electron at vertex 1 to vertex 2. This costs energy 2, and x=(-2,+1,+2,-1).
• Move one positron at vertex 2 to vertex 1. This costs energy 2, and x=(-1,0,+2,-1).
• Move one electron at vertex 4 to vertex 1. This costs energy 3, and x=(-2,0,+2,0).
• Move one electron at vertex 1 to vertex 3. This costs energy 1, and x=(-1,0,+1,0).
• Move one electron at vertex 1 to vertex 3. This costs energy 1, and x=(0,0,0,0).

It is impossible to annihilate all positrons and electrons with energy 8 or less, so the answer is 9.

Sample Input 2

2
0 0
1 2 1

Sample Output 2

0

The condition may already be satisfied from the beginning.

Sample Input 3

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

Sample Output 3

28

Problem Statement

There is a graph G with N vertices and 0 edges on a 2-dimensional plane. The vertices are numbered from 1 to N, and vertex i is located at coordinates (x_i,y_i).

For vertices u and v of G, the distance d(u,v) between u and v is defined as the Manhattan distance d(u,v)=|x_u-x_v|+|y_u-y_v|.

Also, for two connected components A and B of G, let V(A) and V(B) be the vertex sets of A and B, respectively. The distance d(A,B) between A and B is defined as d(A,B)=\min\lbrace d(u,v)\mid u \in V(A), v\in V(B)\rbrace.

Process Q queries as described below. Each query is one of the following three types:

• 1 a b : Let n be the number of vertices in G. Add vertex n+1 to G with coordinates (x_{n+1},y_{n+1})=(a,b).
• 2 : Let n be the number of vertices in G and m be the number of connected components.
  • If m=1, output -1.
  • If m\geq 2, merge all connected components with the minimum distance and output the value of that minimum distance. Formally, let the connected components of G be A_1,A_2,\ldots,A_m and let \displaystyle k=\min_{1\leq i\lt j\leq m} d(A_i,A_j). For all pairs of vertices (u,v)\ (1\leq u\lt v\leq n) that are not in the same connected component and satisfy d(u,v)=k, add an edge between vertices u and v. Then, output k.
• 3 u v : If vertices u and v are in the same connected component, output Yes; otherwise, output No.

Constraints

• 2\leq N\leq 1500
• 1\leq Q\leq 1500
• 0\leq x_i,y_i\leq 10^9
• For queries of type 1, 0\leq a,b\leq 10^9.
• For queries of type 3, let n be the number of vertices in G just before processing that query, then 1\leq u\lt v\leq n.
• All input values are integers.

Sample Input 1

4 11
3 4
3 3
7 3
2 2
3 1 2
2
3 1 2
1 6 4
2
3 2 5
2
3 2 5
2
1 2 2
2

Sample Output 1

No
1
Yes
2
No
3
Yes
-1
0

Initially, vertices 1,2,3,4 are located at coordinates (3,4),(3,3),(7,3),(2,2), respectively.

• For the 1st query, vertices 1 and 2 are not connected, so output No.
• For the 2nd query, there are 4 connected components, and the vertex set of each connected component is \lbrace 1\rbrace, \lbrace 2\rbrace, \lbrace 3\rbrace, \lbrace 4\rbrace. The minimum distance between different connected components is 1, and an edge is added between vertices 1 and 2. Output 1.
• For the 3rd query, vertices 1 and 2 are connected, so output Yes.
• For the 4th query, add vertex 5 at coordinates (6,4).
• For the 5th query, there are 4 connected components, and the vertex set of each connected component is \lbrace 1,2\rbrace,\lbrace 3\rbrace,\lbrace 4\rbrace,\lbrace 5\rbrace. The minimum distance between different connected components is 2, and edges are added between vertices 2 and 4 and between vertices 3 and 5. Output 2.
• For the 6th query, vertices 2 and 5 are not connected, so output No.
• For the 7th query, there are 2 connected components, and the vertex set of each connected component is \lbrace 1,2,4\rbrace,\lbrace 3,5\rbrace. The minimum distance between different connected components is 3, and an edge is added between vertices 1 and 5. Output 3.
• For the 8th query, vertices 2 and 5 are connected, so output Yes.
• For the 9th query, there is 1 connected component, so output -1.
• For the 10th query, add vertex 6 at coordinates (2,2).
• For the 11th query, there are 2 connected components, and the vertex set of each connected component is \lbrace 1,2,3,4,5\rbrace,\lbrace 6\rbrace. The minimum distance between different connected components is 0, and an edge is added between vertices 4 and 6. Output 0.

Problem Statement

You are given an integer N \geq 2 and an integer P between 0 and 100, inclusive. Let p=P/100.

There is a sequence A. Initially, the length of A is 1, and its only element is 1.

The following operation is repeated N-1 times on sequence A:

• Let m be the smallest positive integer that does not appear in A. With probability p, perform operation 1; with probability 1-p, perform operation 2:
  • Operation 1: Append m to the end of A.
  • Operation 2: Let c_1,c_2,\dots,c_{m-1} be the number of times 1,2,\dots,m-1 appear in A, respectively. Choose an integer k between 1 and m-1, inclusive, with probability proportional to c_k. That is, choose k with probability c_k/\sum_{j=1}^{m-1} c_j. Then, append k to the end of A.

For each k=1,2,\dots,N, find the expected number of occurrences of k in A after N-1 operations, modulo 998244353.

Constraints

• 2 \leq N \leq 10^5
• 0 \leq P \leq 100
• All input values are integers.

Sample Input 1

3 50

Sample Output 1

124780546
124780545
748683265

The operations proceed as follows:

• Initially, A=(1).
• 1st operation: It becomes A=(1,2) with probability 1/2, and A=(1,1) with probability 1/2.
• 2nd operation:
  • If A=(1,2), it becomes A=(1,2,3) with probability 1/2, A=(1,2,1) with probability 1/4, and A=(1,2,2) with probability 1/4.
  • If A=(1,1), it becomes A=(1,1,2) with probability 1/2, and A=(1,1,1) with probability 1/2.

The expected numbers of occurrences of 1,2,3 in the final A are \frac{15}{8}, \frac{7}{8}, \frac{1}{4}, respectively.

Sample Input 2

2 0

Sample Output 2

2
0

Sample Input 3

5 24

Sample Output 3

297734288
442981554
937492320
798158491
518366411