Problem Statement

Takahashi has two positive integers A and B.

It is known that A plus B equals N. Find the minimum possible value of "the sum of the digits of A" plus "the sum of the digits of B" (in base 10).

Constraints

• 2 ≤ N ≤ 10^5
• N is an integer.

Sample Input 1

15

Sample Output 1

6

When A=2 and B=13, the sums of their digits are 2 and 4, which minimizes the value in question.

Sample Input 2

100000

Sample Output 2

10

Problem Statement

Takahashi has a tower which is divided into N layers. Initially, all the layers are uncolored. Takahashi is going to paint some of the layers in red, green or blue to make a beautiful tower. He defines the beauty of the tower as follows:

• The beauty of the tower is the sum of the scores of the N layers, where the score of a layer is A if the layer is painted red, A+B if the layer is painted green, B if the layer is painted blue, and 0 if the layer is uncolored.

Here, A and B are positive integer constants given beforehand. Also note that a layer may not be painted in two or more colors.

Takahashi is planning to paint the tower so that the beauty of the tower becomes exactly K. How many such ways are there to paint the tower? Find the count modulo 998244353. Two ways to paint the tower are considered different when there exists a layer that is painted in different colors, or a layer that is painted in some color in one of the ways and not in the other.

Constraints

• 1 ≤ N ≤ 3×10^5
• 1 ≤ A,B ≤ 3×10^5
• 0 ≤ K ≤ 18×10^{10}
• All values in the input are integers.

Sample Input 1

4 1 2 5

Sample Output 1

40

In this case, a red layer worth 1 points, a green layer worth 3 points and the blue layer worth 2 points. The beauty of the tower is 5 when we have one of the following sets of painted layers:

• 1 green, 1 blue
• 1 red, 2 blues
• 2 reds, 1 green
• 3 reds, 1 blue

The total number of the ways to produce them is 40.

Sample Input 2

2 5 6 0

Sample Output 2

1

The beauty of the tower is 0 only when all the layers are uncolored. Thus, the answer is 1.

Sample Input 3

90081 33447 90629 6391049189

Sample Output 3

577742975

Problem Statement

Takahashi and Aoki will play a game with a number line and some segments. Takahashi is standing on the number line and he is initially at coordinate 0. Aoki has N segments. The i-th segment is [L_i,R_i], that is, a segment consisting of points with coordinates between L_i and R_i (inclusive).

The game has N steps. The i-th step proceeds as follows:

• First, Aoki chooses a segment that is still not chosen yet from the N segments and tells it to Takahashi.
• Then, Takahashi walks along the number line to some point within the segment chosen by Aoki this time.

After N steps are performed, Takahashi will return to coordinate 0 and the game ends.

Let K be the total distance traveled by Takahashi throughout the game. Aoki will choose segments so that K will be as large as possible, and Takahashi walks along the line so that K will be as small as possible. What will be the value of K in the end?

Constraints

• 1 ≤ N ≤ 10^5
• -10^5 ≤ L_i < R_i ≤ 10^5
• L_i and R_i are integers.

Sample Input 1

3
-5 1
3 7
-4 -2

Sample Output 1

10

One possible sequence of actions of Takahashi and Aoki is as follows:

• Aoki chooses the first segment. Takahashi moves from coordinate 0 to -4, covering a distance of 4.
• Aoki chooses the third segment. Takahashi stays at coordinate -4.
• Aoki chooses the second segment. Takahashi moves from coordinate -4 to 3, covering a distance of 7.
• Takahashi moves from coordinate 3 to 0, covering a distance of 3.

The distance covered by Takahashi here is 14 (because Takahashi didn't move optimally). It turns out that if both players move optimally, the distance covered by Takahashi will be 10.

Sample Input 2

3
1 2
3 4
5 6

Sample Output 2

12

Sample Input 3

5
-2 0
-2 0
7 8
9 10
-2 -1

Sample Output 3

34

Problem Statement

Takahashi is doing a research on sets of points in a plane. Takahashi thinks a set S of points in a coordinate plane is a good set when S satisfies both of the following conditions:

• The distance between any two points in S is not \sqrt{D_1}.
• The distance between any two points in S is not \sqrt{D_2}.

Here, D_1 and D_2 are positive integer constants that Takahashi specified.

Let X be a set of points (i,j) on a coordinate plane where i and j are integers and satisfy 0 ≤ i,j < 2N.

Takahashi has proved that, for any choice of D_1 and D_2, there exists a way to choose N^2 points from X so that the chosen points form a good set. However, he does not know the specific way to choose such points to form a good set. Find a subset of X whose size is N^2 that forms a good set.

Constraints

• 1 ≤ N ≤ 300
• 1 ≤ D_1 ≤ 2×10^5
• 1 ≤ D_2 ≤ 2×10^5
• All values in the input are integers.

Sample Input 1

2 1 2

Sample Output 1

0 0
0 2
2 0
2 2

Among these points, the distance between 2 points is either 2 or 2\sqrt{2}, thus it satisfies the condition.

Sample Input 2

3 1 5

Sample Output 2

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

Problem Statement

Takahashi loves walking on a tree. The tree where Takahashi walks has N vertices numbered 1 through N. The i-th of the N-1 edges connects Vertex a_i and Vertex b_i.

Takahashi has scheduled M walks. The i-th walk is done as follows:

• The walk involves two vertices u_i and v_i that are fixed beforehand.
• Takahashi will walk from u_i to v_i or from v_i to u_i along the shortest path.

The happiness gained from the i-th walk is defined as follows:

• The happiness gained is the number of the edges traversed during the i-th walk that satisfies one of the following conditions:
  • In the previous walks, the edge has never been traversed.
  • In the previous walks, the edge has only been traversed in the direction opposite to the direction taken in the i-th walk.

Takahashi would like to decide the direction of each walk so that the total happiness gained from the M walks is maximized. Find the maximum total happiness that can be gained, and one specific way to choose the directions of the walks that maximizes the total happiness.

Constraints

• 1 ≤ N,M ≤ 2000
• 1 ≤ a_i , b_i ≤ N
• 1 ≤ u_i , v_i ≤ N
• a_i \neq b_i
• u_i \neq v_i
• The graph given as input is a tree.

Sample Input 1

4 3
2 1
3 1
4 1
2 3
3 4
4 2

Sample Output 1

6
2 3
3 4
4 2

If we decide the directions of the walks as above, he gains the happiness of 2 in each walk, and the total happiness will be 6.

Sample Input 2

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

Sample Output 2

6
2 4
3 5
5 1

Sample Input 3

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

Sample Output 3

9
2 4
6 3
5 6
4 5

Problem Statement

Takahashi and Aoki love calculating things, so they will play with numbers now.

First, they came up with one positive integer each. Takahashi came up with X, and Aoki came up with Y. Then, they will enjoy themselves by repeating the following operation K times:

• Compute the bitwise AND of the number currently kept by Takahashi and the number currently kept by Aoki. Let Z be the result.
• Then, add Z to both of the numbers kept by Takahashi and Aoki.

However, it turns out that even for the two math maniacs this is just too much work. Could you find the number that would be kept by Takahashi and the one that would be kept by Aoki eventually?

Note that input and output are done in binary. Especially, X and Y are given as strings S and T of length N and M consisting of 0 and 1, respectively, whose initial characters are guaranteed to be 1.

Constraints

• 1 ≤ K ≤ 10^6
• 1 ≤ N,M ≤ 10^6
• The initial characters of S and T are 1.

Sample Input 1

2 3 3
11
101

Sample Output 1

10000
10010

The values of X and Y after each operation are as follows:

• After the first operation: (X,Y)=(4,6).
• After the second operation: (X,Y)=(8,10).
• After the third operation: (X,Y)=(16,18).

Sample Input 2

5 8 3
10101
10101001

Sample Output 2

100000
10110100

Sample Input 3

10 10 10
1100110011
1011001101

Sample Output 3

10000100000010001000
10000100000000100010