Problem Statement

In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...

In other words, the IDs are given in the following order:

• the strings of length 1 consisting of uppercase English letters, in lexicographical order;
• the strings of length 2 consisting of uppercase English letters, in lexicographical order;
• the strings of length 3 consisting of uppercase English letters, in lexicographical order;
• ...

Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)

Constraints

• S is a valid ID of a problem given in AtCoder Big Contest.

Sample Input 1

AB

Sample Output 1

28

The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.

Sample Input 2

C

Sample Output 2

3

The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.

Sample Input 3

BRUTMHYHIIZP

Sample Output 3

10000000000000000

The problem whose ID is BRUTMHYHIIZP is the 10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.

Problem Statement

There is a tree T with N vertices. The i-th edge (1\leq i\leq N-1) connects vertex U_i and vertex V_i.

You are given two different vertices X and Y in T. List all vertices along the simple path from vertex X to vertex Y in order, including endpoints.

It can be proved that, for any two different vertices a and b in a tree, there is a unique simple path from a to b.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq X,Y\leq N
• X\neq Y
• 1\leq U_i,V_i\leq N
• All values in the input are integers.
• The given graph is a tree.

Sample Input 1

5 2 5
1 2
1 3
3 4
3 5

Sample Output 1

2 1 3 5

The tree T is shown below. The simple path from vertex 2 to vertex 5 is 2 \to 1 \to 3 \to 5.
Thus, 2,1,3,5 should be printed in this order, with spaces in between.

Sample Input 2

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

Sample Output 2

1 2

The tree T is shown below.

Problem Statement

There is a grid with N \times N squares. We denote by (i, j) the square at the i-th row from the top and j-th column from the left.

Initially, a piece is placed on (1, 1). You may repeat the following operation any number of times:

• Let (i, j) be the square the piece is currently on. Move the piece to the square whose distance from (i, j) is exactly \sqrt{M}.

Here, we define the distance between square (i, j) and square (k, l) as \sqrt{(i-k)^2+(j-l)^2}.

For all squares (i, j), determine if the piece can reach (i, j). If it can, find the minimum number of operations required to do so.

Constraints

• 1 \le N \le 400
• 1 \le M \le 10^6
• All values in the input are integers.

Sample Input 1

3 1

Sample Output 1

0 1 2
1 2 3
2 3 4

You can move the piece to four adjacent squares.

For example, we can move the piece to (2,2) with two operations as follows.

• The piece is now on (1,1). The distance between (1,1) and (1,2) is exactly \sqrt{1}, so move the piece to (1,2).
• The piece is now on (1,2). The distance between (1,2) and (2,2) is exactly \sqrt{1}, so move the piece to (2,2).

Sample Input 2

10 5

Sample Output 2

0 3 2 3 2 3 4 5 4 5
3 4 1 2 3 4 3 4 5 6
2 1 4 3 2 3 4 5 4 5
3 2 3 2 3 4 3 4 5 6
2 3 2 3 4 3 4 5 4 5
3 4 3 4 3 4 5 4 5 6
4 3 4 3 4 5 4 5 6 5
5 4 5 4 5 4 5 6 5 6
4 5 4 5 4 5 6 5 6 7
5 6 5 6 5 6 5 6 7 6

Problem Statement

There are N cities in a certain country.
You will travel from your office in city 1 to a destination in city N, via zero or more cities.
Two types of transportation are available: company car and train. The time required to travel from city i to city j is as follows:

• D_{i,j} \times A minutes by company car, and
• D_{i,j} \times B + C minutes by train.

You can switch from company car to train, but not vice versa.
You can do so without spending time, but only in a city.

What is the minimum time in minutes to travel from city 1 to city N?

Constraints

• 2 \leq N \leq 1000
• 1 \leq A, B, C \leq 10^6
• D_{i,j} \leq 10^6
• D_{i,i} = 0
• D_{i,j} = D_{j,i} > 0 (i \neq j)
• All input values are integers.

Sample Input 1

4 8 5 13
0 6 2 15
6 0 3 5
2 3 0 13
15 5 13 0

Sample Output 1

78

You can travel from city 1 to city 4 in a total of 78 minutes by moving as follows.

• Travel by company car from city 1 to city 3. This takes 2 \times 8 = 16 minutes.
• Travel by company car from city 3 to city 2. This takes 3 \times 8 = 24 minutes.
• Travel by train from city 2 to city 4. This takes 5 \times 5 + 13 = 38 minutes.

It is impossible to travel from city 1 to city 4 in less than 78 minutes.

Sample Input 2

3 1 1000000 1000000
0 10 1
10 0 10
1 10 0

Sample Output 2

1

Sample Input 3

5 954257 954213 814214
0 84251 214529 10017 373342
84251 0 91926 32336 164457
214529 91926 0 108914 57762
10017 32336 108914 0 234705
373342 164457 57762 234705 0

Sample Output 3

168604826785

Problem Statement

For a permutation P = (p_1, p_2, \dots, p_N) of (1,2, \dots, N), let us define the score S(P) of P as follows.

• There are N people, numbered 1,2,\dots,N. Additionally, Snuke is there. Initially, Person i (1 \leq i \leq N) has Ball i.
  Each time Snuke screams, every Person i such that i \neq p_i gives their ball to Person p_i simultaneously.
  If, after screaming at least once, every Person i has Ball i, Snuke stops screaming.
  The score is the number of times Snuke screams until he stops. Here, it is guaranteed that the score will be a finite value.

There are N! permutations P of (1,2, \dots, N). Find the sum, modulo 998244353, of the scores of those permutations, each raised to the K-th power.

• Formally, let S_N be the set of the permutations of (1,2, \dots, N). Compute the following: \displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}.

Constraints

• 2 \leq N \leq 50
• 1 \leq K \leq 10^4
• All values in input are integers.

Sample Input 1

2 2

Sample Output 1

5

When N = 2, there are two possible permutations P: (1,2),(2,1).

The score of the permutation (1,2) is found as follows.

• Initially, Person 1 has Ball 1, and Person 2 has Ball 2.
  After Snuke's first scream, Person 1 has Ball 1, and Person 2 has Ball 2.
  Here, every Person i has Ball i, so he stops screaming.
  Thus, the score is 1.

The score of the permutation (2,1) is found as follows.

• Initially, Person 1 has Ball 1, and Person 2 has Ball 2.
  After Snuke's first scream, Person 1 has Ball 2, and Person 2 has Ball 1.
  After Snuke's second scream, Person 1 has Ball 1, and Person 2 has Ball 2.
  Here, every Person i has Ball i, so he stops screaming.
  Thus, the score is 2.

Therefore, the answer in this case is 1^2 + 2^2 = 5.

Sample Input 2

3 3

Sample Output 2

79

All permutations and their scores are listed below.

• (1,2,3): The score is 1.
• (1,3,2): The score is 2.
• (2,1,3): The score is 2.
• (2,3,1): The score is 3.
• (3,1,2): The score is 3.
• (3,2,1): The score is 2.

Thus, we should print 1^3 + 2^3 + 2^3 + 3^3 + 3^3 + 2^3 = 79.

Sample Input 3

50 10000

Sample Output 3

77436607