Problem Statement

Takahashi is a cashier.

There is a cash register with 11 keys: 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The cash register initially displays 0. Whenever he types the key 00, the displayed number is multiplied by 100; whenever he types one of the others, the displayed number is multiplied by 10, and then added by the number written on the key.

Takahashi wants the cash register to display an integer S. At least how many keystrokes are required to make it display S?

Constraints

• 1\leq S\leq 10^{100000}
• S is an integer.

Sample Input 1

40004

Sample Output 1

4

For example, the following four keystrokes make the cash register display 40004. Initially, the cash register displays 0.

• Type the key 4. It now displays 4.
• Type the key 00. It now displays 400.
• Type the key 0. It now displays 4000.
• Type the key 4. It now displays 40004.

He cannot make it display 40004 with three or fewer keystrokes, so 4 should be printed.

Sample Input 2

1355506027

Sample Output 2

10

Sample Input 3

10888869450418352160768000001

Sample Output 3

27

Note that S may not fit into a 64-\operatorname{bit} integer type.

Problem Statement

We have N bags.
Bag i contains L_i balls. The j-th ball (1\leq j\leq L_i) in Bag i has a positive integer a_{i,j} written on it.

We will pick out one ball from each bag.
How many ways are there to pick the balls so that the product of the numbers written on the picked balls is X?

Here, we distinguish all balls, even with the same numbers written on them.

Constraints

• N \geq 2
• L_i \geq 2
• The product of the numbers of balls in the bags is at most 10^5: \displaystyle\prod_{i=1}^{N}L_i \leq 10^5.
• 1 \leq a_{i,j} \leq 10^9
• 1 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

2 40
3 1 8 4
2 10 5

Sample Output 1

2

When choosing the 3-rd ball in Bag 1 and 1-st ball in Bag 2, we have a_{1,3} \times a_{2,1} = 4 \times 10 = 40.
When choosing the 2-nd ball in Bag 1 and 2-nd ball in Bag 2, we have a_{1,2} \times a_{2,2} = 8 \times 5 = 40.
There are no other ways to make the product 40, so the answer is 2.

Sample Input 2

3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

Sample Output 2

45

Note that we distinguish all balls, even with the same numbers written on them.

Sample Input 3

3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

Sample Output 3

0

There may be no way to make the product X.

Problem Statement

Takahashi has decided to give one gift to Aoki and one gift to Snuke.
There are N candidates of gifts for Aoki, and their values are A_1, A_2, \ldots,A_N.
There are M candidates of gifts for Snuke, and their values are B_1, B_2, \ldots,B_M.

Takahashi wants to choose gifts so that the difference in values of the two gifts is at most D.

Determine if he can choose such a pair of gifts. If he can, print the maximum sum of values of the chosen gifts.

Constraints

• 1\leq N,M\leq 2\times 10^5
• 1\leq A_i,B_i\leq 10^{18}
• 0\leq D \leq 10^{18}
• All values in the input are integers.

Sample Input 1

2 3 2
3 10
2 5 15

Sample Output 1

8

The difference of values of the two gifts should be at most 2.
If he gives a gift with value 3 to Aoki and another with value 5 to Snuke, the condition is satisfied, achieving the maximum possible sum of values.
Thus, 3+5=8 should be printed.

Sample Input 2

3 3 0
1 3 3
6 2 7

Sample Output 2

-1

He cannot choose gifts to satisfy the condition. Note that the candidates of gifts for a person may contain multiple gifts with the same value.

Sample Input 3

1 1 1000000000000000000
1000000000000000000
1000000000000000000

Sample Output 3

2000000000000000000

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

Sample Input 4

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

Sample Output 4

14

Problem Statement

Let us call a positive integer n that satisfies the following condition an arithmetic number.

• Let d_i be the i-th digit of n from the top (when n is written in base 10 without unnecessary leading zeros.) Then, (d_2-d_1)=(d_3-d_2)=\dots=(d_k-d_{k-1}) holds, where k is the number of digits in n.
  • This condition can be rephrased into the sequence (d_1,d_2,\dots,d_k) being arithmetic.
  • If n is a 1-digit integer, it is assumed to be an arithmetic number.

For example, 234,369,86420,17,95,8,11,777 are arithmetic numbers, while 751,919,2022,246810,2356 are not.

Find the smallest arithmetic number not less than X.

Constraints

• X is an integer between 1 and 10^{17} (inclusive).

Sample Input 1

152

Sample Output 1

159

The smallest arithmetic number not less than 152 is 159.

Sample Input 2

88

Sample Output 2

88

X itself may be an arithmetic number.

Sample Input 3

8989898989

Sample Output 3

9876543210

Problem Statement

N players, player 1, player 2, ..., player N, participate in a game tournament. Just before the tournament starts, each player forms a one-person team, so there are N teams in total.

The tournament has a total of N-1 matches. In each match, two different teams are chosen. One team goes first, and the other goes second. Each match will result in exactly one team winning. Specifically, for each i = 1, 2, \ldots, N-1, the i-th match proceeds as follows.

• The team with player p_i goes first, and the team with player q_i goes second.
• Let a and b be the numbers of players in the first and second teams, respectively. The first team wins with probability \frac{a}{a+b}, and the second team wins with probability \frac{b}{a+b}.
• Then, the two teams are combined into a single team.

The result of each match is independent of those of the others.

For each of the N players, print the expected number of times the team with that player wins throughout the tournament, modulo 998244353.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq p_i, q_i \leq N
• Just before the i-th match, player p_i and player q_i belong to different teams.
• All input values are integers.

Sample Input 1

5
1 2
4 3
5 3
1 4

Sample Output 1

698771048 698771048 964969543 964969543 133099248

We call a team formed by player x_1, player x_2, \ldots, player x_k as team \lbrace x_1, x_2, \ldots, x_k \rbrace.

• The first match is played by team \lbrace 1 \rbrace, with player 1, and team \lbrace 2 \rbrace, with player 2. Team \lbrace 1 \rbrace wins with probability \frac{1}{2}, and team \lbrace 2 \rbrace wins with probability \frac{1}{2}. Then, the two teams are combined into a single team \lbrace 1, 2 \rbrace.
• The second match is played by team \lbrace 4 \rbrace, with player 4, and team \lbrace 3 \rbrace, with player 3. Team \lbrace 4 \rbrace wins with probability \frac{1}{2}, and team \lbrace 3 \rbrace wins with probability \frac{1}{2}. Then, the two teams are combined into a single team \lbrace 3, 4 \rbrace.
• The third match is played by team \lbrace 5 \rbrace, with player 5, and team \lbrace 3, 4 \rbrace, with player 3. Team \lbrace 5 \rbrace wins with probability \frac{1}{3}, and team \lbrace 3, 4 \rbrace wins with probability \frac{2}{3}. Then, the two teams are combined into a single team \lbrace 3, 4, 5 \rbrace.
• The fourth match is played by team \lbrace 1, 2 \rbrace, with player 1, and team \lbrace 3, 4, 5 \rbrace, with player 4. Team \lbrace 1, 2 \rbrace wins with probability \frac{2}{5}, and team \lbrace 3, 4, 5 \rbrace wins with probability \frac{3}{5}. Then, the two teams are combined into a single team \lbrace 1, 2, 3, 4, 5 \rbrace.

The expected numbers of times the teams with players 1, 2, 3, 4, 5 win throughout the tournament, E_1, E_2, E_3, E_4, E_5, are \frac{9}{10}, \frac{9}{10}, \frac{53}{30}, \frac{53}{30}, \frac{14}{15}, respectively.

Sample Input 2

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

Sample Output 2

43970290 310168785 806914186 501498951 950708909 272140427 335124893 168750835 310168785 168750835 280459129 280459129 272140427 476542843 43970290