Problem Statement

Print a number between A and B (inclusive) that is a multiple of C.

If there is no such number, print -1.

Constraints

• 1 \leq A \leq B \leq 1000
• 1 \leq C \leq 1000
• All values in input are integers.

Sample Input 1

123 456 100

Sample Output 1

200

300 or 400 would also be accepted.

Sample Input 2

630 940 314

Sample Output 2

-1

Problem Statement

You are given integers A and B, in base K.
Print A \times B in decimal.

Notes

For base-K representation, see Wikipedia's article on Positional notation.

Constraints

• 2 \leq K \leq 10
• 1 \leq A,B \leq 10^5
• A and B are in base-K representation.

Sample Input 1

2
1011 10100

Sample Output 1

220

1011 in base 2 corresponds to 11 in base 10.
10100 in base 2 corresponds to 20 in base 10.
We have 11 \times 20 = 220, so print 220.

Sample Input 2

7
123 456

Sample Output 2

15642

123 in base 7 corresponds to 66 in base 10.
456 in base 7 corresponds to 237 in base 10.
We have 66 \times 237 = 15642, so print 15642.

Problem Statement

We have a sequence of N positive integers: A=(A_1,\dots,A_N).
Let B be the concatenation of 10^{100} copies of A.

Consider summing up the terms of B from left to right. When does the sum exceed X for the first time?
In other words, find the minimum integer k such that:

\displaystyle{\sum_{i=1}^{k} B_i \gt X}.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

3
3 5 2
26

Sample Output 1

8

We have B=(3,5,2,3,5,2,3,5,2,\dots).
\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} holds, but the condition is not satisfied when k is 7 or less, so the answer is 8.

Sample Input 2

4
12 34 56 78
1000

Sample Output 2

23

Problem Statement

We have a sequence of N integers between 0 and 9 (inclusive): A=(A_1, \dots, A_N), arranged from left to right in this order.

Until the length of the sequence becomes 1, we will repeatedly do the operation F or G below.

• Operation F: delete the leftmost two values (let us call them x and y) and then insert (x+y)\%10 to the left end.
• Operation G: delete the leftmost two values (let us call them x and y) and then insert (x\times y)\%10 to the left end.

Here, a\%b denotes the remainder when a is divided by b.

For each K=0,1,\dots,9, answer the following question.

Among the 2^{N-1} possible ways in which we do the operations, how many end up with K being the final value of the sequence?
Since the answer can be enormous, find it modulo 998244353.

Constraints

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

Sample Input 1

3
2 7 6

Sample Output 1

1
0
0
0
2
1
0
0
0
0

If we do Operation F first and Operation F second: the sequence becomes (2,7,6)→(9,6)→(5).
If we do Operation F first and Operation G second: the sequence becomes (2,7,6)→(9,6)→(4).
If we do Operation G first and Operation F second: the sequence becomes (2,7,6)→(4,6)→(0).
If we do Operation G first and Operation G second: the sequence becomes (2,7,6)→(4,6)→(4).

Sample Input 2

5
0 1 2 3 4

Sample Output 2

6
0
1
1
4
0
1
1
0
2

Problem Statement

We have a tree with 2^N-1 vertices.
The vertices are numbered 1 through 2^N-1. For each 1\leq i < 2^{N-1}, the following edges exist:

• an undirected edge connecting Vertex i and Vertex 2i,
• an undirected edge connecting Vertex i and Vertex 2i+1.

There is no other edge.

Let the distance between two vertices be the number of edges in the simple path connecting those two vertices.

Find the number, modulo 998244353, of pairs of vertices (i, j) such that the distance between them is D.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq D \leq 2\times 10^6
• All values in input are integers.

Sample Input 1

3 2

Sample Output 1

14

The following figure describes the given tree.

There are 14 pairs of vertices such that the distance between them is 2: (1,4),(1,5),(1,6),(1,7),(2,3),(3,2),(4,1),(4,5),(5,1),(5,4),(6,1),(6,7),(7,1),(7,6).

Sample Input 2

14142 17320

Sample Output 2

11284501

Problem Statement

Given is a tree with N vertices. The vertices are numbered 1,2,\ldots ,N, and the i-th edge is an undirected edge connecting Vertices u_i and v_i.

For each integer i\,(1 \leq i \leq N), find \sum_{j=1}^{N}dis(i,j).

Here, dis(i,j) denotes the minimum number of edges that must be traversed to go from Vertex i to Vertex j.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq u_i < v_i \leq N
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

3
1 2
2 3

Sample Output 1

3
2
3

We have:

dis(1,1)+dis(1,2)+dis(1,3)=0+1+2=3,

dis(2,1)+dis(2,2)+dis(2,3)=1+0+1=2,

dis(3,1)+dis(3,2)+dis(3,3)=2+1+0=3.

Sample Input 2

2
1 2

Sample Output 2

1
1

Sample Input 3

6
1 6
1 5
1 3
1 4
1 2

Sample Output 3

5
9
9
9
9
9

Problem Statement

In the xy-plane, we have N points, each assigned a weight.
The i-th point has the coordinates (X_i,Y_i) and the weight C_i.

We will choose four of the N points to form an isosceles trapezoid whose vertices are the chosen points.
What is the maximum possible total weight of the points chosen here?

If it is impossible to form an isosceles trapezoid, print -1.

We remind you that an isosceles trapezoid is a quadrilateral that satisfies all of the following conditions.

• It is a trapezoid.
• For one of the two parallel sides, the two angles at its ends are equal.

Constraints

• 4 \leq N \leq 1000
• -10^9 \leq X_i,Y_i \leq 10^9
• 1 \leq C_i \leq 10^9
• (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.
• All values in input are integers.

Sample Input 1

5
0 3 10
3 3 10
-1 0 10
2 0 10000
4 0 10

Sample Output 1

40

We can choose Points 1, 2, 3, 5 to form an isosceles trapezoid, with the points having a total weight of 40.
Any other way to choose points would not form an isosceles trapezoid.

Sample Input 2

6
0 1 1
1 4 20
2 7 300
5 6 4000
4 3 50000
3 0 600000

Sample Output 2

650021

Note that a square and a rectangle are also isosceles trapezoids.

Sample Input 3

7
-3 0 1
-2 0 1
-1 0 1
0 0 1
1 0 1
2 0 1
3 0 1

Sample Output 3

-1

We cannot form an isosceles trapezoid.

Problem Statement

AtCoder Town has N intersections and M roads.
Road i connects Intersections A_i and B_i.

Takahashi, the mayor, has decided to install zero or more surveillance cameras at the intersections.
Each intersection can be installed with zero or one surveillance camera.

How many of the 2^N ways to install surveillance cameras monitor an even number of roads?

Here, Road i is said to be monitored when the following condition is satisfied:

a surveillance camera is installed at one or both of Intersections A_i and B_i.

Constraints

• 2 \leq N \leq 40
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i \lt B_i \leq N
• (A_i,B_i) \neq (A_j,B_j) if i \neq j.
• All values in input are integers.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

6

The sets of towns to install surveillance cameras to satisfy the condition are: \{ \} , \{ 2 \} , \{ 1,2 \} ,\{1,3\},\{2,3\},\{1,2,3\}.
Note that it is allowed to install no surveillance camera.

Sample Input 2

20 3
5 6
3 4
1 2

Sample Output 2

458752

The town may not be connected.