Problem Statement

Two boys, A and B, will share N indistinguishable sweets. How many ways are there to do this so that each boy gets a positive integer number of sweets?

Constraints

• N is an integer.
• 1 \leq N \leq 15

Sample Input 1

2

Sample Output 1

1

There is only one way to share the sweets: A and B get one sweet each.

Sample Input 2

1

Sample Output 2

0

Sample Input 3

3

Sample Output 3

2

Problem Statement

Given is an integer N.

Is it possible to add zero or more 0s at the beginning of the string representing N in base ten to get a palindrome?

Constraints

• 0 \leq N \leq 10^9

Sample Input 1

1210

Sample Output 1

Yes

Adding one 0 at the beginning of 1210 results in 01210, a palindrome.

Sample Input 2

777

Sample Output 2

Yes

777 is already a palindrome.

Sample Input 3

123456789

Sample Output 3

No

Problem Statement

Takahashi is standing at the origin of a two-dimensional plane.

By taking one step, he can move to a point whose Euclidian distance from his current position is exactly R (the coordinates of the destination of a move do not have to be integers). There is no other way to move.

Find the minimum number of steps Takahashi has to take before reaching (X, Y).

We remind you that the Euclidian distance between points (x_1,y_1) and (x_2,y_2) is \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}.

Constraints

• 1 \leq R \leq 10^5
• 0 \leq X,Y \leq 10^5
• (X,Y) \neq (0,0)
• All values in input are integers.

Sample Input 1

5 15 0

Sample Output 1

3

He can reach there in three steps: (0,0) \to (5,0) \to (10,0) \to (15,0). This is the minimum number needed: he cannot reach there in two or fewer steps.

Sample Input 2

5 11 0

Sample Output 2

3

One optimal route is (0,0) \to (5,0) \to (8,4) \to (11,0).

Sample Input 3

3 4 4

Sample Output 3

2

One optimal route is (0,0) \to (2-\frac{\sqrt{2}}{2}, 2+\frac{\sqrt{2}}{2}) \to (4,4).

Problem Statement

Given strings S_1,S_2,S_3 consisting of lowercase English letters, solve the alphametic S_1+S_2=S_3.

Formally, determine whether there is a triple of positive integers N_1, N_2, N_3 satisfying all of the three conditions below, and find one such triple if it exists.
Here, N'_1, N'_2, N'_3 are strings representing N_1, N_2, N_3 (without leading zeros) in base ten, respectively.

• N'_i and S_i have the same number of characters.
• N_1+N_2=N_3.
• The x-th character of S_i and the y-th character of S_j is the same if and only if the x-th character of N'_i and the y-th character of N'_j are the same.

Constraints

• Each of S_1, S_2, S_3 is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.

Sample Input 1

a
b
c

Sample Output 1

1
2
3

Outputs such as (N_1, N_2, N_3) = (4,5,9) will also be accepted, but (1,1,2) will not since it violates the third condition (both a and b correspond to 1).

Sample Input 2

x
x
y

Sample Output 2

1
1
2

Outputs such as (N_1, N_2, N_3) = (3,3,6) will also be accepted, but (1,2,3) will not since it violates the third condition (both 1 and 2 correspond to x).

Sample Input 3

p
q
p

Sample Output 3

UNSOLVABLE

Sample Input 4

abcd
efgh
ijkl

Sample Output 4

UNSOLVABLE

Sample Input 5

send
more
money

Sample Output 5

9567
1085
10652

Problem Statement

Given is a tree with N vertices numbered 1 through N. The i-th edge connects Vertex A_i and Vertex B_i. Vertex i is painted in color C_i (in this problem, colors are represented as integers).

Vertex x is said to be good when the shortest path from Vertex 1 to Vertex x does not contain a vertex painted in the same color as Vertex x, except Vertex x itself.

Find all good vertices.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq C_i \leq 10^5
• 1 \leq A_i,B_i \leq N
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
2
3
4
6

For example, the shortest path from Vertex 1 to Vertex 6 contains Vertices 1,2,3,6. Among them, only Vertex 6 itself is painted in the same color as Vertex 6, so it is a good vertex.
On the other hand, the shortest path from Vertex 1 to Vertex 5 contains Vertices 1,2,5, and Vertex 1 is painted in the same color as Vertex 5, so Vertex 5 is not a good vertex.

Sample Input 2

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

Sample Output 2

1
2
3
5
6
7
8

Problem Statement

Let us write a positive integer on each face of a cube. How many ways are there to do this so that the sum of the six numbers written is S?

Here, two ways to write numbers are not distinguished when they only differ by rotation. (Numbers have no direction.)

The count can be enormous, so find it modulo 998244353.

Constraints

• 6 \leq S \leq 10^{18}
• S is an integer.

Sample Input 1

8

Sample Output 1

3

We have one way to write 1,1,1,1,1,3 on the cube and two ways to write 1,1,1,1,2,2 (one where we write 2 on adjacent faces and another where we write 2 on opposite faces), for a total of three ways.

Sample Input 2

9

Sample Output 2

5

Sample Input 3

50

Sample Output 3

80132

Sample Input 4

10000000000

Sample Output 4

2239716

Find the count modulo 998244353.