Problem Statement

Serval, Fennec, and Raccoon played rock-paper-scissors and had a draw.

You are given characters x and y representing the hand thrown by Fennec and Raccoon, respectively. Here, 0 stands for rock, 1 stands for scissors, and 2 stands for paper.

Print the character corresponding to the hand thrown by Serval, which can be uniquely determined.

Constraints

• Each of x and y is 0, 1, or 2.

Sample Input 1

0 1

Sample Output 1

2

Fennec threw rock, and Raccoon threw scissors. To have a draw, Serval must have thrown paper.

Sample Input 2

0 0

Sample Output 2

0

Fennec threw rock, and Raccoon threw rock. To have a draw, Serval must have thrown rock.

Problem Statement

There are N trees. The i-th tree bears A_i nuts.

Chipmunk will harvest nuts from the trees in the following manner:

• From a tree with 10 or fewer nuts, she does not take nuts.
• From a tree with more than 10 nuts, she takes all but 10 nuts.

Find the total number of nuts Chipmunk will take from the trees.

Constraints

• 1 \leq N \leq 1000
• 0 \leq A_i \leq 1000
• All values in input are integers.

Sample Input 1

3
6 17 28

Sample Output 1

25

From the three trees, Chipmunk will take 0, 7, and 18 nuts, for a total of 25 nuts.

Sample Input 2

4
8 9 10 11

Sample Output 2

1

Problem Statement

The republic of AtCoder has N cities numbered 1 through N and M roads numbered 1 through M.

Road i leads from City A_i to City B_i, but you cannot use it to get from City B_i to City A_i.

Puma is planning her journey where she starts at some city, travels along zero or more roads, and finishes at some city.

How many pairs of cities can be the origin and destination of Puma's journey? We distinguish pairs with the same set of cities in different orders.

Constraints

• 2 \leq N \leq 2000
• 0 \leq M \leq \min(2000,N(N-1))
• 1 \leq A_i,B_i \leq N
• A_i \neq B_i
• (A_i,B_i) are distinct.
• All values in input are integers.

Sample Input 1

3 3
1 2
2 3
3 2

Sample Output 1

7

We have seven pairs of cities that can be the origin and destination: (1,1),(1,2),(1,3),(2,2),(2,3),(3,2),(3,3).

Sample Input 2

3 0

Sample Output 2

3

We have three pairs of cities that can be the origin and destination: (1,1),(2,2),(3,3).

Sample Input 3

4 4
1 2
2 3
3 4
4 1

Sample Output 3

16

Every pair of cities can be the origin and destination.

Problem Statement

Takahashi is going to cook N dishes called Dish 1 through N.

Dish i can be cooked by using an oven for T_i consecutive minutes. An oven cannot be used for two or more dishes simultaneously.

If Takahashi has two ovens to use, what is the shortest number of minutes needed to cook all the N dishes? Assume that all processes other than using ovens take negligible time.

Constraints

• 1 \leq N \leq 100
• 1 \leq T_i \leq 10^3
• All values in input are integers.

Sample Input 1

5
8 3 7 2 5

Sample Output 1

13

We can, for example, use the two ovens as follows to cook all the dishes in 13 minutes.

• The first oven: Cook Dishes 5 and 1 in this order.
• The second oven: Cook Dishes 2, 4, and 3 in this order.

Sample Input 2

2
1000 1

Sample Output 2

1000

Sample Input 3

9
3 14 15 9 26 5 35 89 79

Sample Output 3

138

Problem Statement

The Republic of AtCoder has N cities and M roads.

The cities are numbered 1 through N, and the roads are numbered 1 through M. Road i connects City A_i and City B_i bidirectionally.

There is a rush hour in the country that peaks at time 0. If you start going through Road i at time t, it will take C_i+ \left\lfloor \frac{D_i}{t+1} \right\rfloor time units to reach the other end. (\lfloor x\rfloor denotes the largest integer not exceeding x.)

Takahashi is planning to depart City 1 at time 0 or some integer time later and head to City N.

Print the earliest time when Takahashi can reach City N if he can stay in each city for an integer number of time units. It can be proved that the answer is an integer under the Constraints of this problem.

If City N is unreachable, print -1 instead.

Constraints

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

Sample Input 1

2 1
1 2 2 3

Sample Output 1

4

We will first stay in City 1 until time 1. Then, at time 1, we will start going through Road 1, which will take 2+\left\lfloor \frac{3}{1+1} \right\rfloor = 3 time units before reaching City 2 at time 4.

It is impossible to reach City 2 earlier than time 4.

Sample Input 2

2 3
1 2 2 3
1 2 2 1
1 1 1 1

Sample Output 2

3

There may be multiple roads connecting the same pair of cities, and a road going from a city to the same city.

Sample Input 3

4 2
1 2 3 4
3 4 5 6

Sample Output 3

-1

There may be no path from City 1 to City N.

Sample Input 4

6 9
1 1 0 0
1 3 1 2
1 5 2 3
5 2 16 5
2 6 1 10
3 4 3 4
3 5 3 10
5 6 1 100
4 2 0 110

Sample Output 4

20

Problem Statement

We have a rectangular room that is H meters long and W meters wide.
We will fill this entire room with tatami (rectangular mats) that are 2 meters long and 1 meter wide, and hanjo (square mats) that are 1 meter long and 1 meter wide. Each tatami can be placed vertically or horizontally.
How many ways are there to fill the room?
We distinguish ways that match only after rotation or reflection.

Since the count can be enormous, find it modulo 998244353.

Constraints

• 1 \leq H \leq 6
• 1 \leq W \leq 10^{12}

Sample Input 1

2 2

Sample Output 1

7

We have the following seven ways:

Sample Input 2

3 3

Sample Output 2

131

Sample Input 3

5 100

Sample Output 3

379944232

Be sure to find the count modulo 998244353.