C - 周期的な追いかけっこ 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

数直線上で、高橋君と青木君が追いかけっこをします。青木君は正の方向へ逃げ、高橋君はそれを追いかけます。

二人の速さは N 秒周期で変化します。はじめに長さ N の速さの表が与えられ、その i 番目 (1 \leq i \leq N) には青木君の速さ A_i と高橋君の速さ B_i が定められています。

時刻は 0 から始まります。各非負整数 s について、時刻 s から時刻 s + 1 までの 1 秒間には、速さの表の i = (s \bmod N) + 1 番目が使われます。すなわち、この 1 秒間で青木君は A_i、高橋君は B_i だけ正の方向へ進みます。この対応は N 秒ごとに同じ順序で繰り返されます。

あなたは Q 個の指示を順に処理します。指示には次の 2 種類があります。

  • 1 i a b：速さの表の i 番目を変更し、青木君の速さを a、高橋君の速さを b にする。
  • 2 d：現在の速さの表に基づき、以下の問いに答える。時刻 0 に高橋君が座標 0、青木君が座標 d にいるとして、高橋君が青木君に追い付く最小の非負整数時刻を求めよ。追い付けない場合は -1 を出力せよ。

ここで、追い付くとは、ある非負整数時刻 t において高橋君の座標が青木君の座標以上になることを意味します。判定は整数時刻のみで行い、二人の途中の位置は考慮しません。

各 2 の指示は独立であり、二人の位置は次の指示に引き継がれません。一方、1 の指示による速さの表の変更は、それ以降のすべての指示に引き継がれます。

制約

  • 1 \leq N \leq 3000
  • 1 \leq Q \leq 10^5
  • NQ \leq 10^7
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_i \leq 10^9
  • 1 の指示について：1 \leq i \leq N、0 \leq a \leq 10^9、0 \leq b \leq 10^9
  • 2 の指示について：1 \leq d \leq 10^{15}
  • 2 の指示は 1 つ以上存在する
  • 入力はすべて整数である

入力

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
query_1
query_2
\vdots
query_Q

1 行目に周期 N と指示の個数 Q が与えられる。続く N 行の i 行目に A_i と B_i が与えられる。続く Q 行に指示が 1 i a b または 2 d の形式で与えられる。各行の値はスペース区切りである。

出力

各 2 の指示に対して、高橋君が青木君に追い付く最小の非負整数時刻を 1 行に出力してください。永遠に追い付けない場合は -1 を出力してください。

入力例 1

3 5
2 5
4 3
1 2
2 1
2 4
1 2 0 6
2 8
2 20

出力例 1

1
4
2
6

入力例 2

3 5
2 1
0 2
1 0
2 2
2 1
1 2 5 5
2 1
2 100

出力例 2

-1
2
-1
-1

入力例 3

8 14
5 8
7 4
3 6
10 2
0 5
4 4
6 9
2 1
2 3
2 10
1 4 1 12
2 15
1 8 5 20
2 30
1 2 10 10
2 7
2 100
1 5 8 0
2 12
1 4 0 0
2 25
2 1

出力例 3

1
33
5
8
4
21
4
16
1

入力例 4

20 30
100 150
80 60
0 200
300 100
50 50
20 70
90 30
10 110
400 0
0 0
15 45
60 90
120 80
5 205
700 900
1000 500
30 31
45 40
200 250
75 125
2 1000
2 100000
1 9 0 1000
2 5000
1 16 100 1000
2 20000
1 4 0 0
1 7 0 300
2 12345
2 999999999999999
1 1 1000 0
2 100
1 10 0 1000000000
2 1000000000
1 10 1000000000 0
2 1000000000
1 15 900 700
1 20 125 75
2 7777
2 42
1 2 0 0
1 3 500 100
2 314159
1 18 0 100
2 271828
1 5 0 0
2 1000000000000000
1 12 1000000000 1000000000
2 600
2 600000

出力例 4

-1
-1
89
156
80
6459948320415
9
10
-1
-1
9
-1
-1
-1
-1
-1

入力例 5

1 8
1000000000 0
2 1
1 1 0 0
2 1
1 1 0 1000000000
2 1000000000000000
2 1
1 1 1000000000 1000000000
2 1

出力例 5

-1
-1
1000000
1
-1

Score : 366 pts

Problem Statement

On a number line, Takahashi and Aoki are playing a game of chase. Aoki runs in the positive direction, and Takahashi chases after him.

Their speeds change with a period of N seconds. Initially, a speed table of length N is given, where the i-th entry (1 \leq i \leq N) specifies Aoki's speed A_i and Takahashi's speed B_i.

Time starts from 0. For each non-negative integer s, during the 1-second interval from time s to time s + 1, the i = (s \bmod N) + 1-th entry of the speed table is used. That is, during this 1 second, Aoki moves A_i and Takahashi moves B_i in the positive direction. This correspondence repeats in the same order every N seconds.

You process Q queries in order. There are two types of queries:

  • 1 i a b: Change the i-th entry of the speed table so that Aoki's speed becomes a and Takahashi's speed becomes b.
  • 2 d: Based on the current speed table, answer the following question. Assuming that at time 0, Takahashi is at coordinate 0 and Aoki is at coordinate d, find the minimum non-negative integer time at which Takahashi catches up to Aoki. If he can never catch up, output -1.

Here, catching up means that at some non-negative integer time t, Takahashi's coordinate is greater than or equal to Aoki's coordinate. The check is performed only at integer times; the positions of the two in between are not considered.

Each 2 query is independent, and the positions of the two are not carried over to the next query. On the other hand, changes to the speed table made by 1 queries are carried over to all subsequent queries.

Constraints

  • 1 \leq N \leq 3000
  • 1 \leq Q \leq 10^5
  • NQ \leq 10^7
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_i \leq 10^9
  • For 1 queries: 1 \leq i \leq N, 0 \leq a \leq 10^9, 0 \leq b \leq 10^9
  • For 2 queries: 1 \leq d \leq 10^{15}
  • There is at least one 2 query
  • All input values are integers

Input

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
query_1
query_2
\vdots
query_Q

The first line gives the period N and the number of queries Q. The following N lines give A_i and B_i on the i-th line. The following Q lines give queries in the format 1 i a b or 2 d. Values on each line are separated by spaces.

Output

For each 2 query, output on one line the minimum non-negative integer time at which Takahashi catches up to Aoki. If he can never catch up, output -1.

Sample Input 1

3 5
2 5
4 3
1 2
2 1
2 4
1 2 0 6
2 8
2 20

Sample Output 1

1
4
2
6

Sample Input 2

3 5
2 1
0 2
1 0
2 2
2 1
1 2 5 5
2 1
2 100

Sample Output 2

-1
2
-1
-1

Sample Input 3

8 14
5 8
7 4
3 6
10 2
0 5
4 4
6 9
2 1
2 3
2 10
1 4 1 12
2 15
1 8 5 20
2 30
1 2 10 10
2 7
2 100
1 5 8 0
2 12
1 4 0 0
2 25
2 1

Sample Output 3

1
33
5
8
4
21
4
16
1

Sample Input 4

20 30
100 150
80 60
0 200
300 100
50 50
20 70
90 30
10 110
400 0
0 0
15 45
60 90
120 80
5 205
700 900
1000 500
30 31
45 40
200 250
75 125
2 1000
2 100000
1 9 0 1000
2 5000
1 16 100 1000
2 20000
1 4 0 0
1 7 0 300
2 12345
2 999999999999999
1 1 1000 0
2 100
1 10 0 1000000000
2 1000000000
1 10 1000000000 0
2 1000000000
1 15 900 700
1 20 125 75
2 7777
2 42
1 2 0 0
1 3 500 100
2 314159
1 18 0 100
2 271828
1 5 0 0
2 1000000000000000
1 12 1000000000 1000000000
2 600
2 600000

Sample Output 4

-1
-1
89
156
80
6459948320415
9
10
-1
-1
9
-1
-1
-1
-1
-1

Sample Input 5

1 8
1000000000 0
2 1
1 1 0 0
2 1
1 1 0 1000000000
2 1000000000000000
2 1
1 1 1000000000 1000000000
2 1

Sample Output 5

-1
-1
1000000
1
-1