Problem Statement

Let xyz denote the 3-digit integer whose digits are x, y, z from left to right.

Given a 3-digit integer abc none of whose digits is 0, find abc+bca+cab.

Constraints

• abc is a 3-digit integer abc none of whose digits is 0.

Sample Input 1

123

Sample Output 1

666

We have 123+231+312=666.

Sample Input 2

999

Sample Output 2

2997

We have 999+999+999=2997.

Problem Statement

There are N platforms arranged in a row. The height of the i-th platform from the left is H_i.

Takahashi is initially standing on the leftmost platform.

Since he likes heights, he will repeat the following move as long as possible.

• If the platform he is standing on is not the rightmost one, and the next platform to the right has a height greater than that of the current platform, step onto the next platform.

Find the height of the final platform he will stand on.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq H_i \leq 10^9
• All values in input are integers.

Sample Input 1

5
1 5 10 4 2

Sample Output 1

10

Takahashi is initially standing on the leftmost platform, whose height is 1. The next platform to the right has a height of 5 and is higher than the current platform, so he steps onto it.

He is now standing on the 2-nd platform from the left, whose height is 5. The next platform to the right has a height of 10 and is higher than the current platform, so he steps onto it.

He is now standing on the 3-rd platform from the left, whose height is 10. The next platform to the right has a height of 4 and is lower than the current platform, so he stops moving.

Thus, the height of the final platform Takahashi will stand on is 10.

Sample Input 2

3
100 1000 100000

Sample Output 2

100000

Sample Input 3

4
27 1828 1828 9242

Sample Output 3

1828

Problem Statement

We have a sequence of N numbers: A = (a_1, a_2, \dots, a_N).
Process the Q queries explained below.

• Query i: You are given a pair of integers (x_i, k_i). Let us look at the elements of A one by one from the beginning: a_1, a_2, \dots Which element will be the k_i-th occurrence of the number x_i?
  Print the index of that element, or -1 if there is no such element.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq a_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
• 1 \leq k_i \leq N (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

6 8
1 1 2 3 1 2
1 1
1 2
1 3
1 4
2 1
2 2
2 3
4 1

Sample Output 1

1
2
5
-1
3
6
-1
-1

1 occurs in A at a_1, a_2, a_5. Thus, the answers to Query 1 through 4 are 1, 2, 5, -1 in this order.

Sample Input 2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

Sample Output 2

2
-1

Problem Statement

We have a positive integer a. Additionally, there is a blackboard with a number written in base 10.
Let x be the number on the blackboard. Takahashi can do the operations below to change this number.

• Erase x and write x multiplied by a, in base 10.
• See x as a string and move the rightmost digit to the beginning.
  This operation can only be done when x \geq 10 and x is not divisible by 10.

For example, when a = 2, x = 123, Takahashi can do one of the following.

• Erase x and write x \times a = 123 \times 2 = 246.
• See x as a string and move the rightmost digit 3 of 123 to the beginning, changing the number from 123 to 312.

The number on the blackboard is initially 1. What is the minimum number of operations needed to change the number on the blackboard to N? If there is no way to change the number to N, print -1.

Constraints

• 2 \leq a \lt 10^6
• 2 \leq N \lt 10^6
• All values in input are integers.

Sample Input 1

3 72

Sample Output 1

4

We can change the number on the blackboard from 1 to 72 in four operations, as follows.

• Do the operation of the first type: 1 \to 3.
• Do the operation of the first type: 3 \to 9.
• Do the operation of the first type: 9 \to 27.
• Do the operation of the second type: 27 \to 72.

It is impossible to reach 72 in three or fewer operations, so the answer is 4.

Sample Input 2

2 5

Sample Output 2

-1

It is impossible to change the number on the blackboard to 5.

Sample Input 3

2 611

Sample Output 3

12

There is a way to change the number on the blackboard to 611 in 12 operations: 1 \to 2 \to 4 \to 8 \to 16 \to 32 \to 64 \to 46 \to 92 \to 29 \to 58 \to 116 \to 611, which is the minimum possible.

Sample Input 4

2 767090

Sample Output 4

111

Problem Statement

Given is a weighted undirected connected graph G with N vertices and M edges, which may contain self-loops and multi-edges.
The vertices are labeled as Vertex 1, Vertex 2, \dots, Vertex N.
The edges are labeled as Edge 1, Edge 2, \ldots, Edge M. Edge i connects Vertex a_i and Vertex b_i and has a weight of c_i. Here, for every pair of integers (i, j) such that 1 \leq i \lt j \leq M, c_i \neq c_j holds.

Process the Q queries explained below.
The i-th query gives a triple of integers (u_i, v_i, w_i). Here, for every integer j such that 1 \leq j \leq M, w_i \neq c_j holds.
Let e_i be an undirected edge that connects Vertex u_i and Vertex v_i and has a weight of w_i. Consider the graph G_i obtained by adding e_i to G. It can be proved that the minimum spanning tree T_i of G_i is uniquely determined. Does T_i contain e_i? Print the answer as Yes or No.

Note that the queries do not change T. In other words, even though Query i considers the graph obtained by adding e_i to G, the G in other queries does not have e_i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N - 1 \leq M \leq 2 \times 10^5
• 1 \leq a_i \leq N (1 \leq i \leq M)
• 1 \leq b_i \leq N (1 \leq i \leq M)
• 1 \leq c_i \leq 10^9 (1 \leq i \leq M)
• c_i \neq c_j (1 \leq i \lt j \leq M)
• The graph G is connected.
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq u_i \leq N (1 \leq i \leq Q)
• 1 \leq v_i \leq N (1 \leq i \leq Q)
• 1 \leq w_i \leq 10^9 (1 \leq i \leq Q)
• w_i \neq c_j (1 \leq i \leq Q, 1 \leq j \leq M)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes
No
Yes

Below, let (u,v,w) denote an undirected edge that connects Vertex u and Vertex v and has the weight of w. Here is an illustration of G:

For example, Query 1 considers the graph G_1 obtained by adding e_1 = (1,3,1) to G. The minimum spanning tree T_1 of G_1 has the edge set \lbrace (1,2,2),(1,3,1),(2,4,5),(3,5,8) \rbrace, which contains e_1, so Yes should be printed.

Sample Input 2

2 3 2
1 2 100
1 2 1000000000
1 1 1
1 2 2
1 1 5

Sample Output 2

Yes
No

Problem Statement

Given are M digits C_i.

Find the sum, modulo 998244353, of all integers between 1 and N (inclusive) that contain all of C_1, \ldots, C_M when written in base 10 without unnecessary leading zeros.

Constraints

• 1 \leq N < 10^{10^4}
• 1 \leq M \leq 10
• 0 \leq C_1 < \ldots < C_M \leq 9
• All values in input are integers.

Sample Input 1

104
2
0 1

Sample Output 1

520

Between 1 and 104, there are six integers that contain both 0 and 1 when written in base 10: 10,100,101,102,103,104.
The sum of them is 520.

Sample Input 2

999
4
1 2 3 4

Sample Output 2

0

Between 1 and 999, no integer contains all of 1, 2, 3, 4.

Sample Input 3

1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
5
0 2 4 6 8

Sample Output 3

397365274

Be sure to find the sum modulo 998244353.

Problem Statement

Takahashi has A apple seedlings, B banana seedlings, and C cherry seedlings. Seedlings of the same kind cannot be distinguished.
He will plant these seedlings in his N gardens so that all of the following conditions are satisfied.

• At least one seedling must be planted in every garden.
• It is not allowed to plant two or more seedlings of the same kind in the same garden.
• It is not necessary to plant all seedlings he has.

How many ways are there to plant seedlings to satisfy the conditions? Find the count modulo 998244353.
Two ways are distinguished when there is a garden with different sets of seedlings planted in these two ways.

Constraints

• 1 \leq N \leq 5 \times 10^6
• 0 \leq A \leq N
• 0 \leq B \leq N
• 0 \leq C \leq N
• All values in input are integers.

Sample Input 1

2 2 1 1

Sample Output 1

21

As illustrated below, there are 21 ways to plant seedlings to satisfy the conditions.
(The two frames arranged vertically are the gardens. A, B, C stand for apple, banana, cherry, respectively.)

Sample Input 2

2 0 0 0

Sample Output 2

0

There may be no way to plant seedlings to satisfy the conditions.

Sample Input 3

2 0 2 2

Sample Output 3

9

Sample Input 4

100 12 34 56

Sample Output 4

769445780

Sample Input 5

5000000 2521993 2967363 3802088

Sample Output 5

264705492

Problem Statement

Given is an undirected graph with N vertices and M edges. The i-th edge connects Vertices A_i and B_i and has a weight of C_i.

Initially, all vertices are painted black. You can do the following operation at most K times.

• Operation: choose any vertex v and any integer x. Paint red all vertices reachable from the vertex v by traversing edges whose weights are at most x, including v itself.

How many sets can be the set of vertices painted red after the operations?
Find the count modulo 998244353.

Constraints

• 2 \leq N \leq 10^5
• 0 \leq M \leq 10^5
• 1 \leq K \leq 500
• 1 \leq A_i,B_i \leq N
• 1 \leq C_i \leq 10^9
• All values in input are integers.

Sample Input 1

3 2 1
1 2 1
2 3 2

Sample Output 1

6

For example, an operation with (v,x)=(2,1) paints Vertices 1,2 red, and an operation with (v,x)=(1,0) paints Vertex 1.

After at most one operation, the set of vertices painted red can be one of the following six: \{\},\{1\},\{2\},\{3\},\{1,2\},\{1,2,3\}.

Sample Input 2

5 0 2

Sample Output 2

16

The given graph may not be connected.

Sample Input 3

6 8 2
1 2 1
2 3 2
3 4 3
4 5 1
5 6 2
6 1 3
1 2 10
1 1 100

Sample Output 3

40

The given graph may have multi-edges and self-loops.