Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N and positive integers P,Q,R, and S.
Here, P,Q,R, and S satisfy 1\leq P\leq Q<R\leq S \leq N and Q-P=S-R.

Let B=(B_1, B_2,\ldots, B_N) be the sequence obtained by swapping the P-th through Q-th terms and the R-th through S-th terms of A.
Print the sequence B.

Constraints

• 1\leq N \leq 100
• 1\leq A_i\leq 100
• 1\leq P\leq Q<R\leq S \leq N
• Q-P=S-R
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

5 6 7 4 1 2 3 8

Swapping the 1-st through 3-rd terms (1,2,3) and the 5-th through 7-th terms (5,6,7) of the sequence A=(1,2,3,4,5,6,7,8) results in B=(5,6,7,4,1,2,3,8), which should be printed with spaces in between.

Sample Input 2

5 2 3 4 5
2 2 1 1 1

Sample Output 2

2 1 1 2 1

The same integer may occur multiple times in the sequence.

Sample Input 3

2 1 1 2 2
50 100

Sample Output 3

100 50

Sample Input 4

10 2 4 7 9
22 75 26 45 72 81 47 29 97 2

Sample Output 4

22 47 29 97 72 81 75 26 45 2

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

• N is an integer between 1 and 1000, inclusive.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.

Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.

Sample Input 3

8
national

Sample Output 3

nyationyal

Problem Statement

You are given a string S of length N. Let S_i\ (1\leq i \leq N) be the i-th character of S from the left.

You may perform the following two kinds of operations zero or more times in any order:

• Pay A yen (the currency in Japan). Move the leftmost character of S to the right end. In other words, change S_1S_2\ldots S_N to S_2\ldots S_NS_1.

• Pay B yen. Choose an integer i between 1 and N, and replace S_i with any lowercase English letter.

How many yen do you need to pay to make S a palindrome?

Constraints

• 1\leq N \leq 5000
• 1\leq A,B\leq 10^9
• S is a string of length N consisting of lowercase English letters.
• All values in the input except for S are integers.

Sample Input 1

5 1 2
rrefa

Sample Output 1

3

First, pay 2 yen to perform the operation of the second kind once: let i=5 to replace S_5 with e. S is now rrefe.

Then, pay 1 yen to perform the operation of the first kind once. S is now refer, which is a palindrome.

Thus, you can make S a palindrome for 3 yen. Since you cannot make S a palindrome for 2 yen or less, 3 is the answer.

Sample Input 2

8 1000000000 1000000000
bcdfcgaa

Sample Output 2

4000000000

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

Problem Statement

Takahashi has N kinds of coins; specifically, for 1\leq i\leq N, he has B_i coins worth A_i yen (the currency in Japan) each.

Determine if Takahashi can pay exactly X yen (without change) with the coins he currently has.

Constraints

• 1\leq N\leq 50
• 1\leq X\leq 10^4
• 1\leq A_i\leq 100
• 1\leq B_i\leq 50
• A_i are pairwise distinct.
• All values in the input are integers.

Sample Input 1

2 19
2 3
5 6

Sample Output 1

Yes

Takahashi has three 2-yen coins and six 5-yen coins. He can use two 2-yen coins and three 5-yen coins to pay exactly 2\times 2+5\times 3=19 yen. Thus, Yes should be printed.

Sample Input 2

2 18
2 3
5 6

Sample Output 2

No

There is no combination of the coins that he can use to pay exactly 18 yen. Thus, No should be printed.

Sample Input 3

3 1001
1 1
2 1
100 10

Sample Output 3

Yes

He need not use all kinds of coins.

Problem Statement

There are N cities. There are also one-way direct flights that connect different cities.
The availability of direct flights is represented by N strings S_1,S_2,\ldots,S_N of length N each. If the j-th character of S_i is Y, there is a direct flight from city i to city j; if it is N, there is not.
Each city sells a souvenir; city i sells a souvenir of value A_i.

Consider the following problem:

Takahashi is currently at city S and wants to get to city T (that is different from city S) using some direct flights.
Every time he visits a city (including S and T), he buys a souvenir there.
If there are multiple routes from city S to city T, Takahashi decides the route as follows:

• He tries to minimize the number of direct flights in the route from city S to city T.
• Then he tries to maximize the total value of the souvenirs he buys.

Determine if he can travel from city S to city T using the direct flights. If he can, find the "number of direct flights" and "total value of souvenirs" in the route that satisfies the conditions above.

You are given Q pairs (U_i,V_i) of distinct cities.
For each 1\leq i\leq Q, print the answer to the problem above when S=U_i and T=V_i.

Constraints

• 2 \leq N \leq 300
• 1\leq A_i\leq 10^9
• S_i is a string of length N consisting of Y and N.
• The i-th character of S_i is N.
• 1\leq Q\leq N(N-1)
• 1\leq U_i,V_i\leq N
• U_i\neq V_i
• If i \neq j, then (U_i,V_i)\neq (U_j,V_J).
• N,A_i,Q,U_i, and V_i are all integers.

Sample Input 1

5
30 50 70 20 60
NYYNN
NNYNN
NNNYY
YNNNN
YNNNN
3
1 3
3 1
4 5

Sample Output 1

1 100
2 160
3 180

For (S,T)=(U_1,V_1)=(1,3), there is a direct flight from city 1 to city 3, so the minimum possible number of direct flights is 1, which is achieved when he uses that direct flight. In this case, the total value of the souvenirs is A_1+A_3=30+70=100.

For (S,T)=(U_2,V_2)=(3,1), the minimum possible number of direct flights is 2. The following two routes achieve the minimum: cities 3\to 4\to 1, and cities 3\to 5\to 1. Since the total value of souvenirs in the two routes are 70+20+30=120 and 70+60+30=160, respectively, so he chooses the latter route, and the total value of the souvenirs is 160.

For (S,T)=(U_3,V_3)=(4,5), the number of direct flights is minimum when he travels cities 4\to 1\to 3\to 5, where the total value of the souvenirs is 20+30+70+60=180.

Sample Input 2

2
100 100
NN
NN
1
1 2

Sample Output 2

Impossible

There may be no direct flight at all.

Problem Statement

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

You and the judge will follow the procedure below. The procedure consists of phases 1 and 2; phase 1 is immediately followed by phase 2.

(Phase 1)

• The judge decides an integer N between 1 and 10^9 (inclusive), which is hidden.
• You print an integer M between 1 and 110 (inclusive).
• You also print an integer sequence A=(A_1,A_2,\ldots,A_M) of length M such that 1 \leq A_i \leq M for all i = 1, 2, \ldots, M.

(Phase 2)

• The judge gives you an integer sequence B=(B_1,B_2,\ldots,B_M) of length M. Here, B_i = f^N(i). f(i) is defined by f(i)=A_i for all integers i between 1 and M (inclusive), and f^N(i) is the integer resulting from replacing i with f(i) N times.
• Based on the given B, you identify the integer N that the judge has decided, and print N.

After the procedure above, terminate the program immediately to be judged correct.

Constraints

• N is an integer between 1 and 10^9 (inclusive).

Input and Output

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

(Phase 1)

• First, print an integer M between 1 and 110 (inclusive). It must be followed by a newline.

M

• Then, print a sequence A=(A_1,A_2,\ldots,A_M) of length M consisting of integers between 1 and M (inclusive), with spaces in between. It must be followed by a newline.

A_1 A_2 \ldots A_M

(Phase 2)

• First, an integer sequence B=(B_1,B_2,\ldots,B_M) of length M is given from the input.

B_1 B_2 \ldots B_M

• Find the integer N and print it. It must be followed by a newline.

N

If you print something illegal, the judge prints -1. In that case, your submission is already considered incorrect. Since the judge program terminates at this point, it is desirable that your program terminates too.

Notes

• After each output, add a newline and then flush Standard Output. Otherwise, you may get a TLE verdict.
• If an invalid output is printed during the interaction, or if the program terminates halfway, the verdict will be indeterminate.
• After you print the answer (or you receive -1), immediately terminate the program normally. Otherwise, the verdict will be indeterminate.
• Note that an excessive newline is also considered an invalid input.

Sample Interaction

The following is a sample interaction with N = 2.

Problem Statement

You are given a simple connected undirected graph G with N vertices and M edges.
The vertices of G are numbered vertex 1, vertex 2, \ldots, and vertex N, and its edges are numbered edge 1, edge 2, \ldots, and edge M. Edge i connects vertex U_i and vertex V_i.
You are also given a subset of the edges: S=\{x_1,x_2,\ldots,x_K\}.

Determine if there is a walk on G that contains edge x exactly once for all x \in S.
The walk may contain an edge not in S any number of times (possibly zero).

Constraints

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq \min(\frac{N(N-1)}{2},2\times 10^5)
• 1 \leq U_i<V_i\leq N
• If i\neq j, then (U_i,V_i)\neq (U_j,V_j) .
• G is connected.
• 1 \leq K \leq M
• 1 \leq x_1<x_2<\cdots<x_K \leq M
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

Yes

The walk (v_1,e_1,v_3,e_3,v_4,e_4,v_5,e_6,v_6,e_5,v_4,e_3,v_3,e_2,v_2) satisfies the condition, where v_i denotes vertex i and e_i denotes edge i.
In other words, the walk travels the vertices on G in this order: 1\to 3\to 4\to 5\to 6\to 4\to 3\to 2.
This walk satisfies the condition because it contains edges 1, 2, 4, and 5 exactly once each.

Sample Input 2

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

Sample Output 2

No

There is no walk that contains edges 1, 2, and 3 exactly once each, so No should be printed.

Problem Statement

On a two-dimensional plane, there is a convex polygon C with N vertices, and points S=(s_x, s_y) and T=(t_x,t_y). The vertices of C are (x_1,y_1),(x_2,y_2),\ldots, and (x_N,y_N) in counterclockwise order. It is guaranteed that S and T are outside the polygon.

Find the shortest distance that needs to be traveled to get from point S to point T without entering the interior of C except for its circumference.

Constraints

• 3\leq N \leq 10^5
• |x_i|,|y_i|,|s_x|,|s_y|,|t_x|,|t_y|\leq 10^9
• (x_1,y_1),(x_2,y_2),\ldots, and (x_N,y_N) form a convex polygon in counterclockwise order.
• No three points of C are colinear.
• S and T are outside C and not on the circumference of C.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

5.65028153987288474496

One way to achieve the shortest distance is shown in the following figure.

If you travel as (0,2) \to (1,3) \to(3,3)\to(5,2), the length of the path from point S to point T is 5.650281.... We can prove that it is the minimum. Note that you may enter the circumference of C.

Note that your output is considered correct if the absolute or relative error is at most 10^{-6}. For example, output like 5.650287 is also considered correct.

Sample Input 2

3
0 0
2 0
1 10
3 7
10 3

Sample Output 2

8.06225774829854965279