Problem Statement

You are given a sequence of N integers: A=(A _ 1,A _ 2,\ldots,A _ N).

Print all even numbers in A without changing the order.

Constraints

• 1\leq N\leq 100
• 1\leq A _ i\leq 100\ (1\leq i\leq N)
• A contains at least one even number.
• All values in the input are integers.

Sample Input 1

5
1 2 3 5 6

Sample Output 1

2 6

We have A=(1,2,3,5,6). Among them are two even numbers, A _ 2=2 and A _ 5=6, so print 2 and 6 in this order, with a space in between.

Sample Input 2

5
2 2 2 3 3

Sample Output 2

2 2 2

A may contain equal elements.

Sample Input 3

10
22 3 17 8 30 15 12 14 11 17

Sample Output 3

22 8 30 12 14

Problem Statement

You are given an integer K.

Print a string that is a concatenation of the first K uppercase English letters in ascending order, starting from A.

Constraints

• K is an integer between 1 and 26, inclusive.

Sample Input 1

3

Sample Output 1

ABC

The uppercase English letters in ascending order are A, B, C, ...

By concatenating the first three uppercase English letters, we get ABC.

Sample Input 2

1

Sample Output 2

A

Problem Statement

There are N people. The family name and given name of the i-th person (1 \leq i \leq N) are S_i and T_i, respectively.

Determine whether there is a pair of people with the same family and given names. In other words, determine whether there is a pair of integers (i,j) such that 1 \leq i \lt j \leq N, S_i=S_j, and T_i=T_j.

Constraints

• 2 \leq N \leq 1000
• N is an integer.
• Each of S_i and T_i is a string of length between 1 and 10 (inclusive) consisting of English lowercase letters.

Sample Input 1

3
tanaka taro
sato hanako
tanaka taro

Sample Output 1

Yes

The first and third persons have the same family and given names.

Sample Input 2

3
saito ichiro
saito jiro
saito saburo

Sample Output 2

No

No two persons have the same family and given names.

Sample Input 3

4
sypdgidop bkseq
bajsqz hh
ozjekw mcybmtt
qfeysvw dbo

Sample Output 3

No

Problem Statement

You are given integer sequences, each of length N: A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_N).
All elements of A are different. All elements of B are different, too.

Print the following two values.

1. The number of integers contained in both A and B, appearing at the same position in the two sequences. In other words, the number of integers i such that A_i = B_i.
2. The number of integers contained in both A and B, appearing at different positions in the two sequences. In other words, the number of pairs of integers (i, j) such that A_i = B_j and i \neq j.

Constraints

• 1 \leq N \leq 1000
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• A_1, A_2, \dots, A_N are all different.
• B_1, B_2, \dots, B_N are all different.
• All values in input are integers.

Sample Input 1

4
1 3 5 2
2 3 1 4

Sample Output 1

1
2

There is one integer contained in both A and B, appearing at the same position in the two sequences: A_2 = B_2 = 3.
There are two integers contained in both A and B, appearing at different positions in the two sequences: A_1 = B_3 = 1 and A_4 = B_1 = 2.

Sample Input 2

3
1 2 3
4 5 6

Sample Output 2

0
0

In both 1. and 2., no integer satisfies the condition.

Sample Input 3

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

Sample Output 3

3
2

Problem Statement

Takahashi has placed N gifts on a number line. The i-th gift is placed at coordinate A_i.

You will choose a half-open interval [x,x+M) of length M on the number line and acquire all the gifts included in it.
More specifically, you acquire gifts according to the following procedure.

• First, choose one real number x.
• Then, acquire all the gifts whose coordinates satisfy x \le A_i < x+M.

What is the maximum number of gifts you can acquire?

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le M \le 10^9
• 0 \le A_i \le 10^9

Sample Input 1

8 6
2 3 5 7 11 13 17 19

Sample Output 1

4

For example, specify the half-open interval [1.5,7.5).
In this case, you can acquire the four gifts at coordinates 2,3,5,7, the maximum number of gifts that can be acquired.

Sample Input 2

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

Sample Output 2

2

There may be multiple gifts at the same coordinate.

Sample Input 3

10 998244353
100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853

Sample Output 3

7

Problem Statement

We have a multiset of integers S, which is initially empty.

Given Q queries, process them in order. Each query is of one of the following types.

• 1 x: Insert an x into S.

• 2 x c: Remove an x from S m times, where m = \mathrm{min}(c,( the number of x's contained in S)).

• 3 : Print ( maximum value of S)-( minimum value of S). It is guaranteed that S is not empty when this query is given.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 0 \leq x \leq 10^9
• 1 \leq c \leq Q
• When a query of type 3 is given, S is not empty.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
5
4

The multiset S transitions as follows.

• 1-st query: insert 3 into S. S is now \lbrace 3 \rbrace.
• 2-nd query: insert 2 into S. S is now \lbrace 2, 3 \rbrace.
• 3-rd query: the maximum value of S = \lbrace 2, 3\rbrace is 3 and its minimum value is 2, so print 3-2=1.
• 4-th query: insert 2 into S. S is now \lbrace 2,2,3 \rbrace.
• 5-th query: insert 7 into S. S is now \lbrace 2, 2,3, 7\rbrace.
• 6-th query: the maximum value of S = \lbrace 2,2,3, 7\rbrace is 7 and its minimum value is 2, so print 7-2=5.
• 7-th query: since there are two 2's in S and \mathrm{min(2,3)} = 2, remove 2 from S twice. S is now \lbrace 3, 7\rbrace.
• 8-th query: the maximum value of S = \lbrace 3, 7\rbrace is 7 and its minimum value is 3, so print 7-3=4.

Sample Input 2

4
1 10000
1 1000
2 100 3
1 10

Sample Output 2

If the given queries do not contain that of type 3, nothing should be printed.

Problem Statement

For a positive integer N, let V_N be the integer formed by concatenating N exactly N times.
More precisely, consider N as a string, concatenate N copies of it, and treat the result as an integer to get V_N.
For example, V_3=333 and V_{10}=10101010101010101010.

Find the remainder when V_N is divided by 998244353.

Constraints

• 1 \leq N \leq 10^{18}
• N is an integer.

Sample Input 1

5

Sample Output 1

55555

The remainder when V_5=55555 is divided by 998244353 is 55555.

Sample Input 2

9

Sample Output 2

1755646

The remainder when V_9=999999999 is divided by 998244353 is 1755646.

Sample Input 3

10000000000

Sample Output 3

468086693

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

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

You are given a permutation P=(P _ 1,P _ 2,\ldots,P _ N) of (1,2,\ldots,N).

Find the following value for all i\ (1\leq i\leq N):

• D _ i=\displaystyle\min_{j\neq i}\left\lparen\left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert\right\rparen.

Constraints

• 2 \leq N \leq 2\times10^5
• 1 \leq P _ i \leq N\ (1\leq i\leq N)
• i\neq j\implies P _ i\neq P _ j
• All values in the input are integers.

Sample Input 1

4
3 2 4 1

Sample Output 1

2 2 3 3 

For example, for i=1,

• if j=2, we have \left\lvert P _ i-P _ j\right\rvert=1 and \left\lvert i-j\right\rvert=1;
• if j=3, we have \left\lvert P _ i-P _ j\right\rvert=1 and \left\lvert i-j\right\rvert=2;
• if j=4, we have \left\lvert P _ i-P _ j\right\rvert=2 and \left\lvert i-j\right\rvert=3.

Thus, the value is minimum when j=2, where \left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert=2, so D _ 1=2.

Sample Input 2

7
1 2 3 4 5 6 7

Sample Output 2

2 2 2 2 2 2 2 

Sample Input 3

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

Sample Output 3

3 3 3 5 3 4 3 3 4 2 2 4 4 4 4 7