A - Don't be late

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 1 \leq D \leq 10000
• 1 \leq T \leq 10000
• 1 \leq S \leq 10000
• 入力は全て整数

### 入力

D T S


### 入力例 1

1000 15 80


### 出力例 1

Yes


### 入力例 2

2000 20 100


### 出力例 2

Yes


### 入力例 3

10000 1 1


### 出力例 3

No


Score : 100 points

### Problem Statement

Takahashi is meeting up with Aoki.

They have planned to meet at a place that is D meters away from Takahashi's house in T minutes from now.

Takahashi will leave his house now and go straight to the place at a speed of S meters per minute.

Will he arrive in time?

### Constraints

• 1 \leq D \leq 10000
• 1 \leq T \leq 10000
• 1 \leq S \leq 10000
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

D T S


### Output

If Takahashi will reach the place in time, print Yes; otherwise, print No.

### Sample Input 1

1000 15 80


### Sample Output 1

Yes


It takes 12.5 minutes to go 1000 meters to the place at a speed of 80 meters per minute. They have planned to meet in 15 minutes so he will arrive in time.

### Sample Input 2

2000 20 100


### Sample Output 2

Yes


It takes 20 minutes to go 2000 meters to the place at a speed of 100 meters per minute. They have planned to meet in 20 minutes so he will arrive just on time.

### Sample Input 3

10000 1 1


### Sample Output 3

No


He will be late.

B - Substring

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

2 つの文字列 S, T が与えられます。

TS の部分文字列となるように、S のいくつかの文字を書き換えます。

ただし、部分文字列とは連続する部分列のことを指します。例えば、xxxyxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。

### 制約

• S,T1 文字以上 1000 文字以下
• T の長さは S の長さ以下
• S,T は 英小文字のみを含む

### 入力

S
T


### 出力

S を書き換える文字数の最小値を出力せよ。

### 入力例 1

cabacc
abc


### 出力例 1

1


S 自身は T を部分文字列に持たないので、この 1 文字を書き換えるのが最小です。

### 入力例 2

codeforces
atcoder


### 出力例 2

6


Score : 200 points

### Problem Statement

Given are two strings S and T.

Let us change some of the characters in S so that T will be a substring of S.

At least how many characters do we need to change?

Here, a substring is a consecutive subsequence. For example, xxx is a substring of yxxxy, but not a substring of xxyxx.

### Constraints

• The lengths of S and T are each at least 1 and at most 1000.
• The length of T is at most that of S.
• S and T consist of lowercase English letters.

### Input

Input is given from Standard Input in the following format:

S
T


### Output

Print the minimum number of characters in S that need to be changed.

### Sample Input 1

cabacc
abc


### Sample Output 1

1


For example, changing the fourth character a in S to c will match the second through fourth characters in S to T.

Since S itself does not have T as its substring, this number of changes - one - is the minimum needed.

### Sample Input 2

codeforces
atcoder


### Sample Output 2

6

C - Sum of product of pairs

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N 個の整数 A_1,\ldots,A_N が与えられます。

1\leq i < j \leq N を満たす全ての組 (i,j) についての A_i \times A_j の和を \bmod (10^9+7) で求めてください。

### 制約

• 2 \leq N \leq 2\times 10^5
• 0 \leq A_i \leq 10^9
• 入力は全て整数

### 入力

N
A_1 \ldots A_N


### 出力

\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} A_i A_j\bmod (10^9+7) で出力せよ。

### 入力例 1

3
1 2 3


### 出力例 1

11


1 \times 2 + 1 \times 3 + 2 \times 3 = 11 です。

### 入力例 2

4
141421356 17320508 22360679 244949


### 出力例 2

437235829


Score : 300 points

### Problem Statement

Given are N integers A_1,\ldots,A_N.

Find the sum of A_i \times A_j over all pairs (i,j) such that 1\leq i < j \leq N, modulo (10^9+7).

### Constraints

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

### Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N


### Output

Print \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} A_i A_j, modulo (10^9+7).

### Sample Input 1

3
1 2 3


### Sample Output 1

11


We have 1 \times 2 + 1 \times 3 + 2 \times 3 = 11.

### Sample Input 2

4
141421356 17320508 22360679 244949


### Sample Output 2

437235829

D - Friends

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

1 から 人 N までの N 人の人がいます。

「人 A_i と人 B_i は友達である」という情報が M 個与えられます。同じ情報が複数回与えられることもあります。

XY が友達、かつ、YZ が友達ならば、XZ も友達です。また、M 個の情報から導くことができない友達関係は存在しません。

### 制約

• 2 \leq N \leq 2\times 10^5
• 0 \leq M \leq 2\times 10^5
• 1\leq A_i,B_i\leq N
• A_i \neq B_i

### 入力

N M
A_1 B_1
\vdots
A_M B_M


### 入力例 1

5 3
1 2
3 4
5 1


### 出力例 1

3


### 入力例 2

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


### 出力例 2

4


### 入力例 3

10 4
3 1
4 1
5 9
2 6


### 出力例 3

3


Score : 400 points

### Problem Statement

There are N persons called Person 1 through Person N.

You are given M facts that "Person A_i and Person B_i are friends." The same fact may be given multiple times.

If X and Y are friends, and Y and Z are friends, then X and Z are also friends. There is no friendship that cannot be derived from the M given facts.

Takahashi the evil wants to divide the N persons into some number of groups so that every person has no friend in his/her group.

At least how many groups does he need to make?

### Constraints

• 2 \leq N \leq 2\times 10^5
• 0 \leq M \leq 2\times 10^5
• 1\leq A_i,B_i\leq N
• A_i \neq B_i

### Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M


### Sample Input 1

5 3
1 2
3 4
5 1


### Sample Output 1

3


Dividing them into three groups such as \{1,3\}, \{2,4\}, and \{5\} achieves the goal.

### Sample Input 2

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


### Sample Output 2

4


### Sample Input 3

10 4
3 1
4 1
5 9
2 6


### Sample Output 3

3

E - Coprime

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N 個の整数があります。i 番目の数は A_i です。

「全ての 1\leq i < j \leq N について、GCD(A_i,A_j)=1」が成り立つとき、\{A_i\} は pairwise coprime であるといいます。

\{A_i\} が pairwise coprime ではなく、かつ、GCD(A_1,\ldots,A_N)=1 であるとき、\{A_i\} は setwise coprime であるといいます。

\{A_i\} が pairwise coprime、setwise coprime、そのどちらでもない、のいずれであるか判定してください。

ただし GCD(\ldots) は最大公約数を表します。

### 制約

• 2 \leq N \leq 10^6
• 1 \leq A_i\leq 10^6

### 入力

N
A_1 \ldots A_N


### 出力

\{A_i\} が pairwise coprime ならば pairwise coprime、setwise coprime ならば setwise coprime、そのどちらでもなければ not coprime と出力せよ。

### 入力例 1

3
3 4 5


### 出力例 1

pairwise coprime


GCD(3,4)=GCD(3,5)=GCD(4,5)=1 なので pairwise coprime です。

### 入力例 2

3
6 10 15


### 出力例 2

setwise coprime


GCD(6,10)=2 なので pairwise coprime ではありませんが、GCD(6,10,15)=1 なので setwise coprime です。

### 入力例 3

3
6 10 16


### 出力例 3

not coprime


GCD(6,10,16)=2 なので、pairwise coprime でも setwise coprime でもありません。

Score : 500 points

### Problem Statement

We have N integers. The i-th number is A_i.

\{A_i\} is said to be pairwise coprime when GCD(A_i,A_j)=1 holds for every pair (i, j) such that 1\leq i < j \leq N.

\{A_i\} is said to be setwise coprime when \{A_i\} is not pairwise coprime but GCD(A_1,\ldots,A_N)=1.

Determine if \{A_i\} is pairwise coprime, setwise coprime, or neither.

Here, GCD(\ldots) denotes greatest common divisor.

### Constraints

• 2 \leq N \leq 10^6
• 1 \leq A_i\leq 10^6

### Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N


### Output

If \{A_i\} is pairwise coprime, print pairwise coprime; if \{A_i\} is setwise coprime, print setwise coprime; if neither, print not coprime.

### Sample Input 1

3
3 4 5


### Sample Output 1

pairwise coprime


GCD(3,4)=GCD(3,5)=GCD(4,5)=1, so they are pairwise coprime.

### Sample Input 2

3
6 10 15


### Sample Output 2

setwise coprime


Since GCD(6,10)=2, they are not pairwise coprime. However, since GCD(6,10,15)=1, they are setwise coprime.

### Sample Input 3

3
6 10 16


### Sample Output 3

not coprime


GCD(6,10,16)=2, so they are neither pairwise coprime nor setwise coprime.

F - I hate Shortest Path Problem

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

H+1 マス横 W マスのマス目があります。

あなたは一番上のいずれかのマスから始めて右か下に一マス移動することを繰り返します。ただし、1 以上 H 以下のそれぞれの整数 i について、グリッドの上から i マス目の左から A_i マス目、A_i + 1 マス目、\ldotsB_i マス目のマスからは下に移動することができません。

1 以上 H 以下のそれぞれの整数 k について、上から k+1 マス目のいずれかのマス目まで移動するための最小の移動回数を求めてください。(出発するマスは各場合について個別に選ぶことができます。) 一番上のどのマスから始めても上から k+1 マス目のいずれのマス目にも移動できない場合、代わりに -1 を出力してください。

### 制約

• 1 \leq H,W \leq 2\times 10^5
• 1 \leq A_i \leq B_i \leq W

### 入力

H W
A_1 B_1
A_2 B_2
:
A_H B_H


### 出力

H 行出力せよ。i 行目には、k=i のときの答えを出力せよ。

### 入力例 1

4 4
2 4
1 1
2 3
2 4


### 出力例 1

1
3
6
-1


k=1 のとき、マス (1,1)(2,1) のように 1 回で移動できます。

k=2 のとき、マス (1,1)(2,1)(2,2)(3,2) のように 3 回で移動できます。

k=3 のとき、マス (1,1)(2,1)(2,2)(3,2)(3,3)(3,4)(4,4) のように 6 回で移動できます。

k=4 のとき、上から 5 マス目のマスに移動する方法はありません。

Score : 600 points

### Problem Statement

There is a grid of squares with H+1 horizontal rows and W vertical columns.

You will start at one of the squares in the top row and repeat moving one square right or down. However, for each integer i from 1 through H, you cannot move down from the A_i-th, (A_i + 1)-th, \ldots, B_i-th squares from the left in the i-th row from the top.

For each integer k from 1 through H, find the minimum number of moves needed to reach one of the squares in the (k+1)-th row from the top. (The starting square can be chosen individually for each case.) If, starting from any square in the top row, none of the squares in the (k+1)-th row can be reached, print -1 instead.

### Constraints

• 1 \leq H,W \leq 2\times 10^5
• 1 \leq A_i \leq B_i \leq W

### Input

Input is given from Standard Input in the following format:

H W
A_1 B_1
A_2 B_2
:
A_H B_H


### Output

Print H lines. The i-th line should contain the answer for the case k=i.

### Sample Input 1

4 4
2 4
1 1
2 3
2 4


### Sample Output 1

1
3
6
-1


Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

For k=1, we need one move such as (1,1)(2,1).

For k=2, we need three moves such as (1,1)(2,1)(2,2)(3,2).

For k=3, we need six moves such as (1,1)(2,1)(2,2)(3,2)(3,3)(3,4)(4,4).

For k=4, it is impossible to reach any square in the fifth row from the top.