Problem Statement

Takahashi is learning AtCoderish Language.

He memorizes AtCoderish words corresponding to English words.

He knows that red, blue, and green in English respectively correspond to SSS, FFF, and MMM in AtCoderish, and he knows no other words.

You are given a string S consisting of lowercase English letters. If S equals an English word that Takahashi knows corresponds to an AtCoderish word, output the AtCoderish word corresponding to S; otherwise, output the string Unknown.

Constraints

• S is a string of length between 1 and 10, inclusive, consisting of English letters.

Sample Input 1

red

Sample Output 1

SSS

red in English corresponds to SSS in AtCoderish.

Sample Input 2

atcoder

Sample Output 2

Unknown

Problem Statement

There is an empty bag.

You are given Q queries. Process these queries in order and output the answer to each type-2 query.

Each query is of one of the following types.

• Type 1: Given as input in the format 1 x. Put a ball with the integer x written on it into the bag.

• Type 2: Given as input in the format 2. Pick out one ball with the minimum integer written on it from the balls in the bag, and report that integer as the answer. This query is not given when the bag contains no balls.

Constraints

• 2 \leq Q \leq 100
• In a type-1 query, 1 \leq x \leq 100.
• When a type-2 query is given, the bag is not empty.
• At least one type-2 query is given.
• All input values are integers.

Sample Input 1

5
1 6
1 7
2
1 1
2

Sample Output 1

6
1

Initially, the bag contains no balls.

The 1st query puts a ball with 6 written on it into the bag.

The 2nd query puts a ball with 7 written on it into the bag.

In the 3rd query, the bag contains a ball with 6 written on it and a ball with 7 written on it, so you pick out the ball with 6 written on it. The answer to this query is 6.

The 4th query puts a ball with 1 written on it into the bag.

In the 5th query, the bag contains a ball with 1 written on it and a ball with 7 written on it, so you pick out the ball with 1 written on it. The answer to this query is 1.

Sample Input 2

8
1 5
1 1
1 1
1 9
2
2
1 2
2

Sample Output 2

1
1
2

The bag may contain multiple balls with the same integer.

Problem Statement

There is a grid with 10^9 rows and 10^9 columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

There are N people on the grid. Initially, the i-th person is at square (R_i, C_i).

The time starts at 0. Each person can do the following move at times 1, 2, 3, 4, \ldots.

• Stay at the current position, or move to an 8-adjacent square. It is forbidden to leave the grid. Formally, let square (i, j) be the current square, and move to one of the squares (i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1) that exists. Assume that the move takes no time.

Find the minimum possible time when the N people are at the same square.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq R_i, C_i \leq 10^9
• All input values are integers.

Sample Input 1

3
2 3
5 1
8 1

Sample Output 1

3

All people will be at square (5, 4) at time 3 if each person moves as follows.

• At time 1, the 1st person moves to square (3, 4), the 2nd person moves to square (6, 2), and the 3rd person moves to square (7, 2).

• At time 2, the 1st person moves to square (4, 4), the 2nd person moves to square (5, 3), and the 3rd person moves to square (6, 3).

• At time 3, the 1st person moves to square (5, 4), the 2nd person moves to square (5, 4), and the 3rd person moves to square (5, 4).

Sample Input 2

5
6 7
6 7
6 7
6 7
6 7

Sample Output 2

0

All people start at the same square.

Sample Input 3

6
91 999999986
53 999999997
32 999999932
14 999999909
49 999999985
28 999999926

Sample Output 3

44

Problem Statement

You are given length-N lowercase English strings S and T, and M pairs of integers (L_1,R_1),(L_2,R_2),\ldots,(L_M,R_M).

Perform the following operation for i=1,2,\ldots,M in order:

• Swap the L_i-th through R_i-th characters of S and the L_i-th through R_i-th characters of T.
  • For example, if S is abcdef, T is ghijkl, and (L_i,R_i)=(3,5), then S and T become abijkf and ghcdel, respectively.

Find the string S after performing the M operations.

Constraints

• 1\leq N\leq 5\times 10^5
• 1\leq M\leq 2\times 10^5
• Each of S and T is a length-N lowercase English strings.
• 1\leq L_i\leq R_i\leq N
• N, M, L_i, and R_i are integers.

Sample Input 1

5 3
apple
lemon
2 4
1 5
5 5

Sample Output 1

lpple

Initially, S and T are apple and lemon, respectively.

• After the operation for i=1, S and T are aemoe and lppln, respectively.
• After the operation for i=2, S and T are lppln and aemoe, respectively.
• After the operation for i=3, S and T are lpple and aemon, respectively.

Thus, the string S after the three operations is lpple.

Sample Input 2

10 5
lemwrbogje
omsjbfggme
5 8
4 8
1 3
6 6
1 4

Sample Output 2

lemwrfogje

Problem Statement

You are given a length-N integer sequence A = (A_1, A_2, \ldots, A_N).

Your goal is to perform the following operation repeatedly so that for every length-L contiguous subarray of A, the sum is a multiple of M.

• Choose an integer i such that 1 \leq i \leq N, and increase the value of A_i by 1.

Find the minimum possible number of operations before achieving the goal.

Constraints

• 1 \leq N, M \leq 500
• 1 \leq L \leq N
• 0 \leq A_i < M
• All input values are integers.

Sample Input 1

4 5 3
4 2 1 3

Sample Output 1

4

By performing the operation once choosing i = 2, twice choosing i = 3, and once choosing i = 4, you get A = (4, 3, 3, 4) with a total of four operations, where every length-3 contiguous subarray sums to a multiple of 5.

Sample Input 2

7 10 4
7 0 9 1 6 4 2

Sample Output 2

10

Problem Statement

You are given N lowercase English strings S_1,S_2,\ldots,S_N, and an integer L.

Find the number, modulo 998244353, of length-L lowercase English strings that contain all of S_1,S_2,\ldots,S_N as substrings.

Constraints

• 1\leq N\leq 8
• 1\leq L\leq 100
• N and L are integers.
• Each S_i is a string of length 1 and 10, inclusive, consisting of lowercase English letters.
• S_i\neq S_j\ (i\neq j)

Sample Input 1

2 4
ab
c

Sample Output 1

153

Some of the strings that satisfy the condition are abcz and cabc. acbd does not contain ab as a substring, so it does not satisfy the condition.

Sample Input 2

2 6
abc
cde

Sample Output 2

54

Sample Input 3

5 50
bbfogggj
zkbach
eedirhyc
ffgd
oemmswj

Sample Output 3

689020583

Problem Statement

You are given a simple connected undirected graph with N vertices numbered 1 to N and M edges. The i-th edge connects vertices u_i and v_i.

For each k=1,2,\ldots,N-1, find the number of simple paths from vertex 1 to vertex N that contain exactly k edges.

Constraints

• 2\leq N\leq 2\times 10^5
• N-1\leq M\leq N+20
• 1\leq u_i\lt v_i\leq N
• The given graph is a simple connected undirected graph.
• All input values are integers.

Sample Input 1

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

Sample Output 1

0 1 2 1

For each k=1,2,3,4, the simple paths from vertex 1 to vertex 5 that contain exactly k edges are as follows.

• k=1 : None
• k=2 : 1\to 3\to 5
• k=3 : 1\to 2\to 4\to 5 and 1\to 3\to 4\to 5
• k=4 : 1\to 2\to 4\to 3\to 5

Sample Input 2

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

Sample Output 2

0 0 0 0 1 5 10 10 5 1

Sample Input 3

7 18
6 7
4 5
1 7
2 7
1 4
2 5
4 6
2 3
5 6
5 7
1 5
2 4
2 6
1 2
1 3
3 4
1 6
3 5

Sample Output 3

1 3 11 29 50 42