Toyota Programming Contest 2024#8（AtCoder Beginner Contest 365）

Please sign in first.

A - Leap Year

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1583 以上 2023 以下の整数 Y が与えられます。

西暦 Y 年の日数を求めてください。

なお、制約の範囲内では西暦 Y 年の日数は以下の通りです。

Y が 4 の倍数でない年は 365 日
Y が 4 の倍数で、かつ 100 の倍数でない年は 366 日
Y が 100 の倍数で、かつ 400 の倍数でない年は 365 日
Y が 400 の倍数である年は 366 日

制約

Y は 1583 以上 2023 以下の整数

入力

入力は以下の形式で標準入力から与えられる。

出力

西暦 Y 年の日数を整数として出力せよ。

入力例 1

出力例 1

2023 は 4 の倍数でないので 365 日です。

入力例 2

出力例 2

1992 は 4 の倍数で、かつ 100 の倍数でないので 366 日です。

入力例 3

出力例 3

1800 は 100 の倍数で、かつ 400 の倍数でないので 365 日です。

入力例 4

出力例 4

1600 は 400 の倍数なので 366 日です。

Score : 100 points

Problem Statement

You are given an integer Y between 1583 and 2023.

Find the number of days in the year Y of the Gregorian calendar.

Within the given range, the year Y has the following number of days:

if Y is not a multiple of 4, then 365 days;
if Y is a multiple of 4 but not a multiple of 100, then 366 days;
if Y is a multiple of 100 but not a multiple of 400, then 365 days;
if Y is a multiple of 400, then 366 days.

Constraints

Y is an integer between 1583 and 2023, inclusive.

Input

The input is given from Standard Input in the following format:

Output

Print the number of days in the year Y as an integer.

Sample Input 1

Sample Output 1

2023 is not a multiple of 4, so it has 365 days.

Sample Input 2

Sample Output 2

1992 is a multiple of 4 but not a multiple of 100, so it has 366 days.

Sample Input 3

Sample Output 3

1800 is a multiple of 100 but not a multiple of 400, so it has 365 days.

Sample Input 4

Sample Output 4

1600 is a multiple of 400, so it has 366 days.

B - Second Best

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の整数列 A=(A_1,\ldots,A_N) が与えられます。ここで A_1,A_2,\ldots,A_N は相異なります。

A の中で二番目に大きい要素は A の何番目の要素でしょうか。

制約

2\leq N\leq 100
1\leq A_i \leq 10^9
A_1,A_2,\ldots,A_N は相異なる
入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N 
A_1 A_2 \ldots A_{N}

出力

A の中で二番目に大きい要素が A の X 番目であるとき、X を整数として出力せよ。

入力例 1

4
8 2 5 1

出力例 1

A の中で二番目に大きい要素は A_3 なので 3 を出力してください。

入力例 2

8
1 2 3 4 5 10 9 11

出力例 2

Score : 200 points

Problem Statement

You are given an integer sequence A=(A_1,\ldots,A_N) of length N. Here, A_1, A_2, \ldots, A_N are all distinct.

Which element in A is the second largest?

Constraints

2 \leq N \leq 100
1 \leq A_i \leq 10^9
A_1, A_2, \ldots, A_N are all distinct.
All input values are integers.

Input

The input is given from Standard Input in the following format:

N 
A_1 A_2 \ldots A_{N}

Output

Print the integer X such that the X-th element in A is the second largest.

Sample Input 1

4
8 2 5 1

Sample Output 1

The second largest element in A is A_3, so print 3.

Sample Input 2

8
1 2 3 4 5 10 9 11

Sample Output 2

C - Transportation Expenses

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

あるイベントには N 人が参加し、i 番目の人の交通費は A_i 円でした。

イベントの主催者である高橋くんは、交通費補助額の上限額 x を設定して、人 i には交通費補助額として \min(x,A_i) 円を支給することとしました。ここで x は非負整数である必要があります。

高橋くんの予算が M 円であり、N 人に渡す交通費補助額の総和を M 円以下にしたいとき、交通費補助額の上限額 x は最大でいくらにできますか？

ただし、交通費補助額の上限額を無限に大きくできる場合は代わりにそのことを報告してください。

制約

1\leq N\leq 2\times 10^5
1\leq M \leq 2\times 10^{14}
1\leq A_i \leq 10^9
入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 A_2 \ldots A_{N}

出力

予算の条件を満たすときの交通費補助額の上限額 x の最大値を整数として出力せよ。

ただし、交通費補助額の上限額を無限に大きくできる場合は代わりに infinite と出力せよ。

入力例 1

4 8
1 3 2 4

出力例 1

交通費補助額の上限額を 2 円にすると、N 人に渡す交通費補助額の総和は \min(2,1) + \min(2,3) + \min(2,2) + \min(2,4) = 7 円となり、予算の 8 円以下となります。

交通費補助額の上限額を 3 円にすると、N 人に渡す交通費補助額の総和は \min(3,1) + \min(3,3) + \min(3,2) + \min(3,4) = 9 円となり、予算の 8 円を超えてしまいます。

よって、交通費補助額の上限額の最大値は 2 円となります。

入力例 2

3 20
5 3 2

出力例 2

infinite

交通費補助額の上限額を無限に大きくできます。

入力例 3

10 23
2 5 6 5 2 1 7 9 7 2

出力例 3

Score : 300 points

Problem Statement

There are N people participating in an event, and the transportation cost for the i-th person is A_i yen.

Takahashi, the organizer of the event, decided to set a maximum limit x for the transportation subsidy. The subsidy for person i will be \min(x, A_i) yen. Here, x must be a non-negative integer.

Given that Takahashi's budget is M yen, and he wants the total transportation subsidy for all N people to be at most M yen, what is the maximum possible value of the subsidy limit x?

If the subsidy limit can be made infinitely large, report that instead.

Constraints

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

Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 \ldots A_{N}

Output

Print the maximum value of the subsidy limit x that satisfies the budget condition, as an integer.

If the subsidy limit can be made infinitely large, print infinite instead.

Sample Input 1

4 8
1 3 2 4

Sample Output 1

If the subsidy limit is set to 2 yen, the total transportation subsidy for all N people is \min(2,1) + \min(2,3) + \min(2,2) + \min(2,4) = 7 yen, which is within the budget of 8 yen.

If the subsidy limit is set to 3 yen, the total transportation subsidy for all N people is \min(3,1) + \min(3,3) + \min(3,2) + \min(3,4) = 9 yen, which exceeds the budget of 8 yen.

Therefore, the maximum possible value of the subsidy limit is 2 yen.

Sample Input 2

3 20
5 3 2

Sample Output 2

infinite

The subsidy limit can be made infinitely large.

Sample Input 3

10 23
2 5 6 5 2 1 7 9 7 2

Sample Output 3

D - AtCoder Janken 3

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋くんと青木くんが N 回のじゃんけんを行いました。

青木くんが出した手は R, P, S からなる長さ N の文字列 S で表されます。青木くんが i 回目 (1\leq i\leq N) のじゃんけんに出した手は、S の i 文字目が R のときグー、P のときパー、S のときチョキです。

高橋くんが出した手について、次の条件を満たすことがわかっています。

高橋くんは青木くんに 1 度も負けなかった。
i=1,2,\ldots,N-1 について、高橋くんが i 回目のじゃんけんに出した手と i+1 回目のじゃんけんに出した手は異なる。

高橋くんが勝った回数としてありえる最大値を求めてください。

ここで、条件を満たすような高橋くんの手が存在することが証明できます。

制約

1\leq N\leq2\times10 ^ 5
S は R, P, S からなる長さ N の文字列
N は整数

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

答えを出力せよ。

入力例 1

6
PRSSRS

出力例 1

青木くんは、6 回のじゃんけんでそれぞれパー、グー、チョキ、チョキ、グー、チョキを出しました。

高橋くんは、それぞれチョキ、パー、グー、チョキ、パー、グーを出すことで、1,2,3,5,6 回目のじゃんけんで勝つことができます。

条件を満たす高橋くんの手のうち 6 回のじゃんけんすべてで勝つものは存在しないため、5 を出力してください。

入力例 2

10
SSSSSSSSSS

出力例 2

入力例 3

24
SPRPSRRRRRPPRPRPSSRSPRSS

出力例 3

Score : 400 points

Problem Statement

Takahashi and Aoki played rock-paper-scissors N times. [Note: In this game, Rock beats Scissors, Scissors beats Paper, and Paper beats Rock.]

Aoki's moves are represented by a string S of length N consisting of the characters R, P, and S. The i-th character of S indicates Aoki's move in the i-th game: R for Rock, P for Paper, and S for Scissors.

Takahashi's moves satisfy the following conditions:

Takahashi never lost to Aoki.
For i=1,2,\ldots,N-1, Takahashi's move in the i-th game is different from his move in the (i+1)-th game.

Determine the maximum number of games Takahashi could have won.

It is guaranteed that there exists a sequence of moves for Takahashi that satisfies these conditions.

Constraints

1\leq N\leq2\times10 ^ 5
S is a string of length N consisting of R, P, and S.
N is an integer.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the maximum number of games Takahashi could have won.

Sample Input 1

6
PRSSRS

Sample Output 1

In the six games of rock-paper-scissors, Aoki played Paper, Rock, Scissors, Scissors, Rock, and Scissors.

Takahashi can play Scissors, Paper, Rock, Scissors, Paper, and Rock to win the 1st, 2nd, 3rd, 5th, and 6th games.

There is no sequence of moves for Takahashi that satisfies the conditions and wins all six games, so print 5.

Sample Input 2

10
SSSSSSSSSS

Sample Output 2

Sample Input 3

24
SPRPSRRRRRPPRPRPSSRSPRSS

Sample Output 3

E - Xor Sigma Problem

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

長さ N の整数列 A=(A_1,\ldots,A_N) が与えられます。次の式の値を求めてください。

\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N (A_i \oplus A_{i+1}\oplus \ldots \oplus A_j)

ビット単位 xor とは

非負整数 A, B のビット単位 xor 、A \oplus B は、以下のように定義されます。

A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。

例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。
一般に k 個の整数 p_1, \dots, p_k の排他的論理和は (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k) と定義され、これは p_1, \dots, p_k の順番によらないことが証明できます。

制約

2\leq N\leq 2\times 10^5
1\leq A_i \leq 10^8
入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N 
A_1 A_2 \ldots A_{N}

出力

答えを出力せよ。

入力例 1

3
1 3 2

出力例 1

A_1\oplus A_2 = 2, A_1 \oplus A_2\oplus A_3 = 0, A_2\oplus A_3 = 1 なので答えは 2+0+1=3 です。

入力例 2

7
2 5 6 5 2 1 7

出力例 2

Score : 450 points

Problem Statement

You are given an integer sequence A=(A_1,\ldots,A_N) of length N. Find the value of the following expression:

\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N (A_i \oplus A_{i+1}\oplus \ldots \oplus A_j).

Notes on bitwise XOR

The bitwise XOR of non-negative integers A and B, denoted as A \oplus B, is defined as follows:

In the binary representation of A \oplus B, the digit at the 2^k (k \geq 0) position is 1 if and only if exactly one of the digits at the 2^k position in the binary representations of A and B is 1; otherwise, it is 0.

For example, 3 \oplus 5 = 6 (in binary: 011 \oplus 101 = 110).
In general, the bitwise XOR of k integers p_1, \dots, p_k is defined as (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k). It can be proved that this is independent of the order of p_1, \dots, p_k.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^8
All input values are integers.

Input

The input is given from Standard Input in the following format:

N 
A_1 A_2 \ldots A_{N}

Output

Print the answer.

Sample Input 1

3
1 3 2

Sample Output 1

A_1 \oplus A_2 = 2, A_1 \oplus A_2 \oplus A_3 = 0, and A_2 \oplus A_3 = 1, so the answer is 2 + 0 + 1 = 3.

Sample Input 2

7
2 5 6 5 2 1 7

Sample Output 2

F - Takahashi on Grid

Time Limit: 5 sec / Memory Limit: 1024 MiB

配点 : 575 点

問題文

平面上に無限個のマスがあります。整数の 2 つ組 (x,y) すべてに対して対応するマスがひとつ存在し、マス (x,y) と呼ぶことにします。

すべてのマスは、それぞれ空きマスか壁マスのどちらか一方です。
長さ N の正整数列 L=(L _ 1,L _ 2,\dotsc,L _ N),U=(U _ 1,U _ 2,\dotsc,U _ N) が与えられます。ここで、i=1,2,\ldots,N について L _ i,U _ i は 1\leq L _ i\leq U _ i\leq10 ^ 9 を満たします。
マス (x,y)\ (1\leq x\leq N,L _ x\leq y\leq U _ x) はすべて空きマスで、それ以外のマスは壁マスです。

高橋くんが空きマスであるマス (x,y) にいるとき、次の行動のいずれかを行うことができます。

マス (x+1,y) が空きマスならば、マス (x+1,y) に移動する。
マス (x-1,y) が空きマスならば、マス (x-1,y) に移動する。
マス (x,y+1) が空きマスならば、マス (x,y+1) に移動する。
マス (x,y-1) が空きマスならば、マス (x,y-1) に移動する。

どの空きマスどうしも、高橋くんが行動を繰り返すことで行き来できることが保証されます。

次の形式の Q 個の質問に答えてください。

i 番目 (1\leq i\leq Q) の質問では整数の 4 つ組 (s _ {x,i},s _ {y,i},t _ {x,i},t _ {y,i}) が与えられるので、高橋くんがマス (s _ {x,i},s _ {y,i}) にいるところからマス (t _ {x,i},t _ {y,i}) に移動するために必要な行動回数の最小値を求めてください。各質問について、与えられる 2 つのマスは空きマスであることが保証されます。

制約

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 かつ 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 かつ L _ {t _ {x,i}}\leq t _ {y,i}\leq U _ {t _ {x,i}}\ (1\leq i\leq Q)
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
L _ 1 U _ 1
L _ 2 U _ 2
\vdots
L _ N U _ N
Q
s _ {x,1} s _ {y,1} t _ {x,1} t _ {y,1}
s _ {x,2} s _ {y,2} t _ {x,2} t _ {y,2}
\vdots
s _ {x,Q} s _ {y,Q} t _ {x,Q} t _ {y,Q}

出力

Q 行にわたって出力せよ。 i 行目 (1\leq i\leq Q) には、i 番目の質問に対する答えを出力せよ。

入力例 1

出力例 1

10
3
14

与えられたマスは以下のようになります。

1 つめの質問では、例えば以下のように移動することでマス (1,4) からマス (6,3) へ 10 回の行動で移動することができます。

9 回以下の行動でマス (1,4) からマス (6,3) へ移動することはできないため、10 を出力してください。

入力例 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

出力例 2

6000000005

出力すべき値が 32\operatorname{bit} 整数に収まらない場合があることに注意してください。

入力例 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

出力例 3

Score : 575 points

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.

Input

The input is given from Standard Input in the following format:

N
L _ 1 U _ 1
L _ 2 U _ 2
\vdots
L _ N U _ N
Q
s _ {x,1} s _ {y,1} t _ {x,1} t _ {y,1}
s _ {x,2} s _ {y,2} t _ {x,2} t _ {y,2}
\vdots
s _ {x,Q} s _ {y,Q} t _ {x,Q} t _ {y,Q}

Output

Print Q lines. The i-th line (1\leq i\leq Q) should contain the answer to the i-th query.

Sample Input 1

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

G - AtCoder Office

Time Limit: 5 sec / Memory Limit: 1024 MiB

配点 : 575 点

問題文

AtCoder 社のオフィスには N 人の高橋くんが所属しています。

AtCoder 社ではオフィスの入退室の記録が取られており、記録が取られはじめてから M 回の入退室が行われました。

i 番目 (1\leq i\leq M) の入退室記録は整数の組 (T _ i,P _ i) で表され、時刻 T _ i に P _ i 番目の高橋くんがオフィスの外にいるならオフィスに入ったことを、オフィスの中にいるならオフィスから出たことを表します。

記録が取られはじめた時点ではどの高橋くんもオフィスの外におり、現在どの高橋くんもオフィスの外にいることがわかっています。

次の形式の Q 個の質問に答えてください。

i 番目 (1\leq i\leq Q) の質問では整数の組 (A _ i,B _ i) が与えられるので、記録を取っていた間に A _ i 番目の高橋くんと B _ i 番目の高橋くんがどちらもオフィスの中にいた時間の長さを求めてください。

制約

2\leq N\leq2\times10 ^ 5
2\leq M\leq2\times10 ^ 5
1\leq T _ 1\lt T _ 2\lt\dotsb\lt T _ M\leq10 ^ 9
1\leq P _ i\leq N\ (1\leq i\leq M)
どの 1\leq p\leq N についても、P _ i=p となる i は偶数個存在する
1\leq Q\leq2\times10 ^ 5
1\leq A _ i\lt B _ i\leq N\ (1\leq i\leq Q)
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
T _ 1 P _ 1
T _ 2 P _ 2
\vdots
T _ M P _ M
Q
A _ 1 B _ 1
A _ 2 B _ 2
\vdots
A _ Q B _ Q

出力

Q 行にわたって出力せよ。 i 行目 (1\leq i\leq Q) には i 番目の質問に対する答えを出力せよ。

入力例 1

出力例 1

20
0
20

3 人の高橋くんがオフィスの中にいた時間はそれぞれ以下の図のようになります。

それぞれの質問に対する答えは以下のようになります。

1 番目の高橋くんと 2 番目の高橋くんが同時にオフィスの中にいた時間は、時刻 20 から時刻 30 の間と時刻 70 から時刻 80 の間の 2 回です。長さはどちらも 10 なので、これらの合計である 20 を出力してください。
1 番目の高橋くんと 3 番目の高橋くんが同時にオフィスの中にいたことはありません。よって、0 を出力してください。
2 番目の高橋くんと 3 番目の高橋くんが同時にオフィスの中にいた時間は、時刻 40 から時刻 60 の間の 1 回です。長さは 20 なので、20 を出力してください。

入力例 2

出力例 2

Score : 575 points

Problem Statement

N people work at the AtCoder office.

The office keeps records of entries and exits, and there have been M entries and exits since the records began.

The i-th (1\leq i\leq M) record is represented by a pair of integers (T_i, P_i), indicating that at time T_i, the P_i-th person either entered the office if they were outside, or exited the office if they were inside.

It is known that all people were outside the office at the beginning of the records, and they are outside now.

Answer Q queries in the following format.

For the i-th (1\leq i\leq Q) query, you are given a pair of integers (A_i, B_i). Find the total length of the periods during which both the A_i-th and B_i-th persons were inside the office since the records began.

Constraints

2\leq N\leq2\times10^5
2\leq M\leq2\times10^5
1\leq T_1\lt T_2\lt\dotsb\lt T_M\leq10^9
1\leq P_i\leq N\ (1\leq i\leq M)
For every 1\leq p\leq N, the number of indices i such that P_i=p is even.
1\leq Q\leq2\times10^5
1\leq A_i\lt B_i\leq N\ (1\leq i\leq Q)
All inputs are integers.

Input

The input is given from Standard Input in the following format:

N M
T_1 P_1
T_2 P_2
\vdots
T_M P_M
Q
A_1 B_1
A_2 B_2
\vdots
A_Q B_Q

Output

Print Q lines. The i-th line (1\leq i\leq Q) should contain the answer to the i-th query.

Sample Input 1

Sample Output 1

20
0
20

The following diagram shows the time each of the three people spent inside the office.

The answers to each query are as follows:

The 1st and 2nd persons were both inside the office from time 20 to time 30 and from time 70 to time 80. The lengths of these two periods are both 10, so print the total, which is 20.
The 1st and 3rd persons were never inside the office at the same time, so print 0.
The 2nd and 3rd persons were both inside the office from time 40 to time 60. The length of this period is 20, so print 20.

Sample Input 2

Sample Output 2