Problem Statement

Your refrigerator has N kinds of ingredients. Let us call them ingredient 1, \dots, ingredient N. You have Q_i grams of ingredient i.

You can make two types of dishes. To make one serving of dish A, you need A_i grams of each ingredient i (1 \leq i \leq N). To make one serving of dish B, you need B_i grams of each ingredient i. You can only make an integer number of servings of each type of dish.

Using only the ingredients in the refrigerator, what is the maximum total number of servings of dishes you can make?

Constraints

• 1 \leq N \leq 10
• 1 \leq Q_i \leq 10^6
• 0 \leq A_i \leq 10^6
• There is an i such that A_i \geq 1.
• 0 \leq B_i \leq 10^6
• There is an i such that B_i \geq 1.
• All input values are integers.

Sample Input 1

2
800 300
100 100
200 10

Sample Output 1

5

This refrigerator has 800 grams of ingredient 1 and 300 grams of ingredient 2.

You can make one serving of dish A with 100 grams of ingredient 1 and 100 grams of ingredient 2, and one serving of dish B with 200 grams of ingredient 1 and 10 grams of ingredient 2.

To make two servings of dish A and three servings of dish B, you need 100 \times 2 + 200 \times 3 = 800 grams of ingredient 1, and 100 \times 2 + 10 \times 3 = 230 grams of ingredient 2, neither of which exceeds the amount available in the refrigerator. In this way, you can make a total of five servings of dishes, but there is no way to make six, so the answer is 5.

Sample Input 2

2
800 300
100 0
0 10

Sample Output 2

38

You can make 8 servings of dish A with 800 grams of ingredient 1, and 30 servings of dish B with 300 grams of ingredient 2, for a total of 38 servings.

Sample Input 3

2
800 300
801 300
800 301

Sample Output 3

0

You cannot make any dishes.

Sample Input 4

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

Sample Output 4

222222

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M.
Edge i \, (i = 1, 2, \dots, M) connects vertices u_i and v_i.

Determine if this graph is a path graph.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
• All values in the input are integers.
• The graph given in the input is simple.

Sample Input 1

4 3
1 3
4 2
3 2

Sample Output 1

Yes

Illustrated below is the given graph, which is a path graph.

Sample Input 2

2 0

Sample Output 2

No

Illustrated below is the given graph, which is not a path graph.

Sample Input 3

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

Sample Output 3

No

Illustrated below is the given graph, which is not a path graph.

Problem Statement

You are given an integer K greater than or equal to 2.
Find the minimum positive integer N such that N! is a multiple of K.

Here, N! denotes the factorial of N. Under the Constraints of this problem, we can prove that such an N always exists.

Constraints

• 2\leq K\leq 10^{12}
• K is an integer.

Sample Input 1

30

Sample Output 1

5

• 1!=1
• 2!=2\times 1=2
• 3!=3\times 2\times 1=6
• 4!=4\times 3\times 2\times 1=24
• 5!=5\times 4\times 3\times 2\times 1=120

Therefore, 5 is the minimum positive integer N such that N! is a multiple of 30. Thus, 5 should be printed.

Sample Input 2

123456789011

Sample Output 2

123456789011

Sample Input 3

280

Sample Output 3

7

Problem Statement

The Republic of AtCoder has N cities, called City 1, City 2, \ldots, City N. Initially, there was a bidirectional road between every pair of different cities, but M of these roads have become unusable due to deterioration over time. More specifically, for each 1\leq i \leq M, the road connecting City U_i and City V_i has become unusable.

Takahashi will go for a K-day trip that starts and ends in City 1. Formally speaking, a K-day trip that starts and ends in City 1 is a sequence of K+1 cities (A_0, A_1, \ldots, A_K) such that A_0=A_K=1 holds and for each 0\leq i\leq K-1, A_i and A_{i+1} are different and there is still a usable road connecting City A_i and City A_{i+1}.

Print the number of different K-day trips that start and end in City 1, modulo 998244353. Here, two K-day trips (A_0, A_1, \ldots, A_K) and (B_0, B_1, \ldots, B_K) are said to be different when there exists an i such that A_i\neq B_i.

Constraints

• 2 \leq N \leq 5000
• 0 \leq M \leq \min\left( \frac{N(N-1)}{2},5000 \right)
• 2 \leq K \leq 5000
• 1 \leq U_i<V_i \leq N
• All pairs (U_i, V_i) are pairwise distinct.
• All values in input are integers.

Sample Input 1

3 1 4
2 3

Sample Output 1

4

There are four different trips as follows.

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

No other trip is valid, so we should print 4.

Sample Input 2

3 3 3
1 2
1 3
2 3

Sample Output 2

0

No road remains usable, so there is no valid trip.

Sample Input 3

5 3 100
1 2
4 5
2 3

Sample Output 3

428417047

Problem Statement

There are infinitely many cells on a plane. For every pair of integers (x,y), there is a corresponding cell, which we will call cell (x,y).

Each cell is either an empty cell or a wall cell.
You are given two sequences of positive integers of length N: L=(L _ 1,L _ 2,\dotsc,L _ N) and U=(U _ 1,U _ 2,\dotsc,U _ N). Here, L _ i and U _ i satisfy 1\leq L _ i\leq U _ i\leq10 ^ 9 for i=1,2,\ldots,N.
All cells (x,y)\ (1\leq x\leq N,L _ x\leq y\leq U _ x) are empty cells, and all other cells are wall cells.

When Takahashi is at an empty cell (x,y), he can perform one of the following actions.

• If cell (x+1,y) is an empty cell, move to cell (x+1,y).
• If cell (x-1,y) is an empty cell, move to cell (x-1,y).
• If cell (x,y+1) is an empty cell, move to cell (x,y+1).
• If cell (x,y-1) is an empty cell, move to cell (x,y-1).

It is guaranteed that he can travel between any two empty cells by repeating his actions.

Answer Q queries in the following format.

For the i-th query (1\leq i\leq Q), you are given a quadruple of integers (s _ {x,i},s _ {y,i},t _ {x,i},t _ {y,i}). Find the minimum number of actions required for Takahashi to move from cell (s _ {x,i},s _ {y,i}) to cell (t _ {x,i},t _ {y,i}). For each query, it is guaranteed that the given two cells are empty cells.

Constraints

• 1\leq N\leq2\times10 ^ 5
• 1\leq L _ i\leq U _ i\leq10 ^ 9\ (1\leq i\leq N)
• \lbrack L _ i,U _ i\rbrack\cap\lbrack L _ {i+1},U _ {i+1}\rbrack\neq\emptyset\ (1\leq i\lt N)
• 1\leq Q\leq2\times10 ^ 5
• 1\leq s _ {x,i}\leq N and L _ {s _ {x,i}}\leq s _ {y,i}\leq U _ {s _ {x,i}}\ (1\leq i\leq Q)
• 1\leq t _ {x,i}\leq N and L _ {t _ {x,i}}\leq t _ {y,i}\leq U _ {t _ {x,i}}\ (1\leq i\leq Q)
• All input values are integers.

Sample Input 1

7
1 5
3 3
1 3
1 1
1 4
2 4
3 5
3
1 4 6 3
1 4 1 1
7 5 1 5

Sample Output 1

10
3
14

The given cells are as follows.

For the first query, for example, Takahashi can move from cell (1,4) to cell (6,3) in ten actions as follows.

It is impossible to move from cell (1,4) to cell (6,3) in nine or fewer actions, so print 10.

Sample Input 2

12
1 1000000000
1000000000 1000000000
1 1000000000
1 1
1 1000000000
1000000000 1000000000
1 1000000000
1 1
1 1000000000
1000000000 1000000000
1 1000000000
1 1
1
1 1 12 1

Sample Output 2

6000000005

Note that the output value may not fit in a 32-bit integer.

Sample Input 3

10
1694 7483
3396 5566
2567 6970
1255 3799
2657 3195
3158 8007
3368 8266
1447 6359
5365 8614
3141 7245
15
3 3911 6 4694
7 5850 10 4641
1 5586 6 4808
2 3401 8 2676
3 3023 6 6923
8 4082 3 6531
6 3216 7 6282
8 5121 8 3459
8 4388 1 6339
6 6001 3 6771
10 5873 8 5780
1 6512 6 6832
8 5345 7 4975
10 4010 8 2355
7 5837 9 6279

Sample Output 3

2218
1212
4009
1077
3903
4228
3067
1662
4344
6385
95
6959
371
4367
444