Problem Statement

A fruit store sells apples.
You may perform the following operations as many times as you want in any order:

• Buy one apple for X yen (the currency in Japan).
• Buy three apples for Y yen.

How much yen do you need to pay to obtain exactly N apples?

Constraints

• 1 \leq X \leq Y \leq 100
• 1 \leq N \leq 100
• All values in input are integers.

Sample Input 1

10 25 10

Sample Output 1

85

Buy three apples for 25 yen three times and one apple for 10 yen, and you will obtain exactly 10 apples for a total of 85 yen.
You cannot obtain exactly 10 apples for a lower cost, so the answer is 85 yen.

Sample Input 2

10 40 10

Sample Output 2

100

It is optimal to buy an apple for 10 yen 10 times.

Sample Input 3

100 100 2

Sample Output 3

200

The only way to obtain exactly 2 apples is to buy an apple for 100 yen twice.

Sample Input 4

100 100 100

Sample Output 4

3400

Problem Statement

You are given a string S consisting of uppercase English letters. Separate each character of S with a space and print them one by one in order.

Constraints

• S is a string consisting of uppercase English letters with a length between 2 and 100, inclusive.

Sample Input 1

ABC

Sample Output 1

A B C

Separate A, B, and C with spaces and print them one by one.

There is no need to print a space after C.

Sample Input 2

ZZZZZZZ

Sample Output 2

Z Z Z Z Z Z Z

Sample Input 3

OOXXOO

Sample Output 3

O O X X O O

Problem Statement

There are N cities numbered 1, \dots, N, and M roads connecting cities.
The i-th road (1 \leq i \leq M) connects city A_i and city B_i.

Print N lines as follows.

• Let d_i be the number of cities directly connected to city i \, (1 \leq i \leq N), and those cities be city a_{i, 1}, \dots, city a_{i, d_i}, in ascending order.
• The i-th line (1 \leq i \leq N) should contain d_i + 1 integers d_i, a_{i, 1}, \dots, a_{i, d_i} in this order, separated by spaces.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) if (i \neq j).
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

3 2 3 6
2 1 5
2 1 6
0
2 2 6
3 1 3 5

The cities directly connected to city 1 are city 2, city 3, and city 6. Thus, we have d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6, so you should print 3, 2, 3, 6 in the first line in this order, separated by spaces.

Note that a_{i, 1}, \dots, a_{i, d_i} must be in ascending order. For instance, it is unacceptable to print 3, 3, 2, 6 in the first line in this order.

Sample Input 2

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

Sample Output 2

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

Problem Statement

N people numbered 1,2,\ldots,N were in M photos. In each of the photos, they stood in a single line. In the i-th photo, the j-th person from the left is person a_{i,j}.

Two people who did not stand next to each other in any of the photos may be in a bad mood.

How many pairs of people may be in a bad mood? Here, we do not distinguish a pair of person x and person y, and a pair of person y and person x.

Constraints

• 2 \leq N \leq 50
• 1 \leq M \leq 50
• 1 \leq a_{i,j} \leq N
• a_{i,1},\ldots,a_{i,N} contain each of 1,\ldots,N exactly once.
• All values in the input are integers.

Sample Input 1

4 2
1 2 3 4
4 3 1 2

Sample Output 1

2

The pair of person 1 and person 4, and the pair of person 2 and person 4, may be in a bad mood.

Sample Input 2

3 3
1 2 3
3 1 2
1 2 3

Sample Output 2

0

Sample Input 3

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

Sample Output 3

6

Problem Statement

There are N types of beans, one bean of each type. The i-th type of bean has a deliciousness of A_i and a color of C_i. The beans are mixed and can only be distinguished by color.

You will choose one color of beans and eat one bean of that color. By selecting the optimal color, maximize the minimum possible deliciousness of the bean you eat.

Constraints

• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq A_i \leq 10^{9}
• 1 \leq C_i \leq 10^{9}
• All input values are integers.

Sample Input 1

4
100 1
20 5
30 5
40 1

Sample Output 1

40

Note that beans of the same color cannot be distinguished from each other.

You can choose color 1 or color 5.

• There are two types of beans of color 1, with deliciousness of 100 and 40. Thus, the minimum deliciousness when choosing color 1 is 40.
• There are two types of beans of color 5, with deliciousness of 20 and 30. Thus, the minimum deliciousness when choosing color 5 is 20.

To maximize the minimum deliciousness, you should choose color 1, so print the minimum deliciousness in that case: 40.

Sample Input 2

10
68 3
17 2
99 2
92 4
82 4
10 3
100 2
78 1
3 1
35 4

Sample Output 2

35

Problem Statement

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

• X is an N-digit positive integer.
• Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
  • 1 \le X_i \le 9 for all integers 1 \le i \le N;
  • |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.

Constraints

• N is an integer.
• 2 \le N \le 10^6

Sample Input 1

4

Sample Output 1

203

Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.

Sample Input 2

2

Sample Output 2

25

Sample Input 3

1000000

Sample Output 3

248860093

Be sure to find the count modulo 998244353.

Problem Statement

The Republic of AtCoder lies on a Cartesian coordinate plane.
It has N towns, numbered 1,2,\dots,N. Town i is at (x_i, y_i), and no two different towns are at the same coordinates.

There are teleportation spells in the nation. A spell is identified by a pair of integers (a,b), and casting a spell (a, b) at coordinates (x, y) teleports you to (x+a, y+b).

Snuke is a great magician who can learn the spell (a, b) for any pair of integers (a, b) of his choice. The number of spells he can learn is also unlimited.
To be able to travel between the towns using spells, he has decided to learn some number of spells so that it is possible to do the following for every pair of different towns (i, j).

• Choose just one spell among the spells learned. Then, repeatedly use just the chosen spell to get from Town i to Town j.

At least how many spells does Snuke need to learn to achieve the objective above?

Constraints

• 2 \leq N \leq 500
• 0 \leq x_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq y_i \leq 10^9 (1 \leq i \leq N)
• (x_i, y_i) \neq (x_j, y_j) if i \neq j.

Sample Input 1

3
1 2
3 6
7 4

Sample Output 1

6

The figure below illustrates the positions of the towns (along with the coordinates of the four corners).

If Snuke learns the six spells below, he can get from Town i to Town j by using one of the spells once for every pair (i,j) (i \neq j), achieving his objective.

• (2, 4)
• (-2, -4)
• (4, -2)
• (-4, 2)
• (-6, -2)
• (6, 2)

Another option is to learn the six spells below. In this case, he can get from Town i to Town j by using one of the spells twice for every pair (i,j) (i \neq j), achieving his objective.

• (1, 2)
• (-1, -2)
• (2, -1)
• (-2, 1)
• (-3, -1)
• (3, 1)

There is no combination of spells that consists of less than six spells and achieve the objective, so we should print 6.

Sample Input 2

3
1 2
2 2
4 2

Sample Output 2

2

The optimal choice is to learn the two spells below:

• (1, 0)
• (-1, 0)

Sample Input 3

4
0 0
0 1000000000
1000000000 0
1000000000 1000000000

Sample Output 3

8

Problem Statement

You are given a weighted simple connected undirected graph with N vertices and M edges, where vertices are numbered 1 to N, and edges are numbered 1 to M. Additionally, a positive integer K is given.
Edge i\ (1\leq i\leq M) connects vertices u_i and v_i and has a weight of w_i.

For a spanning tree T of this graph, the cost of T is defined as the sum, modulo K, of the weights of the edges in T. Find the minimum cost of a spanning tree of this graph.

Constraints

• 2\leq N\leq8
• N-1\leq M\leq\dfrac{N(N-1)}2
• 1\leq K\leq10^{15}
• 1\leq u_i\lt v_i\leq N\ (1\leq i\leq M)
• 0\leq w_i\lt K\ (1\leq i\leq M)
• The given graph is simple and connected.
• All input values are integers.

Sample Input 1

5 6 328
1 2 99
1 3 102
2 3 86
2 4 94
2 5 95
3 4 81

Sample Output 1

33

The given graph is shown below:

The cost of the spanning tree containing edges 1,3,5,6 is (99+86+81+95)\bmod{328}=361\bmod{328}=33. The cost of every spanning tree of this graph is at least 33, so print 33.

Sample Input 2

6 5 998244353
1 2 337361568
1 6 450343304
2 3 61477244
2 5 745383438
4 5 727360840

Sample Output 2

325437688

Print the cost of the only spanning tree of this graph, which is 325437688.

Sample Input 3

8 28 936294041850197
1 2 473294720906780
1 3 743030800139244
1 4 709363019414774
1 5 383643612490312
1 6 557102781022861
1 7 623179288538138
1 8 739618599410809
2 3 857687812294404
2 4 893923168139714
2 5 581822471860662
2 6 740549363586558
2 7 307226438833222
2 8 447399029952998
3 4 636318083622768
3 5 44548707643622
3 6 307262781240755
3 7 12070267388230
3 8 700247263184082
4 5 560567890325333
4 6 704726113717147
4 7 588263818615687
4 8 549007536393172
5 6 779230871080408
5 7 825982583786498
5 8 713928998174272
6 7 751331074538826
6 8 449873635430228
7 8 11298381761479

Sample Output 3

11360716373

Note that the input and the answer may not fit into a 32\operatorname{bit} integer.

Problem Statement

Takahashi has an integer x. Initially, x = 0.

There are N operations. The i-th operation (1 \leq i \leq N) is represented by two integers t_i and y_i as follows:

• If t_i = 1, replace x with y_i.
• If t_i = 2, replace x with x + y_i.

Takahashi may skip any number between 0 and K (inclusive) of the operations. When he performs the remaining operations once each without changing the order, find the maximum possible final value of x.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq N
• t_i \in \{1,2\} \, (1 \leq i \leq N)
• |y_i| \leq 10^9 \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3

If he skips the 5-th operation, x changes as 0 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3, so x results in 3. This is the maximum.

Sample Input 2

1 0
2 -1000000000

Sample Output 2

-1000000000

Sample Input 3

10 3
2 3
2 -1
1 4
2 -1
2 5
2 -9
2 2
1 -6
2 5
2 -3

Sample Output 3

15