시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 6 5 5 83.333%

문제

Beaverland consists of N cities, numbered from 1 to N. There are N − 1 roads connecting cities. The i-th (1 ≤ i ≤ N−1) road connects the city i and the city i+1 bidirectionally. In Beaverland, they use Byou as the unit of time. Each day in Beaverland is 1 000 000 000 Byous long. The moment x Byous (0 ≤ x < 1 000 000 000) after the beginning of a day is called time x. It takes 1 Byou to pass through any of the roads, and the i-th road can be passed through only between time Li and time Ri every day. Specifically, to pass through the i-th road, we must leave the city i or the city i + 1 at time x satisfying Li ≤ x ≤ Ri − 1, and must arrive at the other city at time x + 1.

Bitaro used to be an ordinary Beaver living in Beaverland. However, as he tries to cope with his lateness, he has finally acquired the skill of leaping through time. By using this skill once, he can go back 1 Byou ago. He cannot go back to the day before: if he uses the skill between time 0 and time 1, he will go back to time 0 of the day. He can use this skill only when he is at a city. The position of Bitaro does not change on using the skill.

Bitaro gets tired when he uses the skill. To find ways to travel with fewer number of usage of the skill, he decided to do a thought experiment consisting of Q steps. In the j-th (1 ≤ j ≤ Q) step in the thought experiment, he does one of the followings:

  • Change the duration in which the Pj-th road can be traveled. After the modification, it can be passed through only between time Sj and time Ej.
  • Suppose he is at the city Aj at time Bj. Then, compute the minimum number of usage of the skill to be at the city Cj at time Dj on the day.

He wonders the result of the thought experiment.

Write a program which, given the number of cities in Beaverland, the information of roads, and the details of the thought experiment, calculates the result of the thought experiment.

입력

Read the following data from the standard input. All the values in the input are integers.

N Q
L1 R1
.
.
.
LN−1 RN−1
(Query 1)
.
.
.
(Query Q)

Here, each (Query j) consists of 4 or 5 integers separated by a space. Let Tj be the first integer in it. Then,

  • If Tj = 1, (Query j) consists of 4 integers Tj , Pj, Sj and Ej. This means that, in the j-th step of the thought experiment, the duration in which the Pj-th road can be passed is changed to the interval between time Sj and time Ej.
  • If Tj = 2, (Query j) consists of 5 integers Tj, Aj, Bj, Cj and Dj. This means that, in the j-th step of the thought experiment, your program should compute the minimum number of usage of the skill to be at the city Cj at time Dj on the day, on the assumption that Bitaro is at the city Aj at time Bj.

출력

For each step with T j = 2, write a line containing the minimum number of usage of the skill to the standard output, in order.

제한

  • 1 ≤ N ≤ 300 000.
  • 1 ≤ Q ≤ 300 000.
  • 0 ≤ Li < Ri ≤ 999 999 999 (1 ≤ i ≤ N − 1).
  • 1 ≤ Tj ≤ 2 (1 ≤ j ≤ Q).
  • 1 ≤ Pj ≤ N − 1 (1 ≤ j ≤ Q,Tj = 1).
  • 0 ≤ Sj < Ej ≤ 999 999 999 (1 ≤ j ≤ Q,Tj = 1).
  • 1 ≤ Aj ≤ N (1 ≤ j ≤ Q,Tj = 2).
  • 0 ≤ Bj ≤ 999 999 999 (1 ≤ j ≤ Q,Tj = 2).
  • 1 ≤ Cj ≤ N (1 ≤ j ≤ Q,Tj = 2).
  • 0 ≤ Dj ≤ 999 999 999 (1 ≤ j ≤ Q,Tj = 2).

예제 입력 1

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

예제 출력 1

2
4

In the 1st step of the thought experiment, Bitaro moves from the city 1 to the city 2 in 1 Byou, then moves from the city 2 to the city 3 in 1 Byou to be at the city 3 at time 5. Therefore, by using the skill twice, he can be at the city 3 at time 3.

In the 2nd step of the thought experiment, the duration in which the 2nd road can be passed is changed to the interval between time 0 and time 1.

In the 3rd step of the thought experiment, Bitaro moves from the city 1 to the city 2 in 1 Byou to be at the city 2 at time 4. Then, he uses the skill four times, moves to the city 3 in 1 Byou and wait 2 Byous to be at the city 3 at time 3.

예제 입력 2

5 5
3 5
4 8
2 6
5 10
2 5 3 1 10
2 2 6 5 6
1 3 4 6
2 3 3 4 3
2 4 5 1 5

예제 출력 2

4
3
2
3

예제 입력 3

7 7
112103440 659752416
86280800 902409187
104535475 965602300
198700180 945132880
137957976 501365807
257419446 565237610
2 4 646977260 7 915994878
2 1 221570340 6 606208433
2 7 948545948 4 604273995
2 7 247791098 5 944822313
2 7 250362511 2 50167280
2 3 364109400 4 555412865
2 7 33882587 7 186961394

예제 출력 3

145611455
0
447180143
0
207252171
0
0

예제 입력 4

7 7
535825574 705426142
964175291 996597835
481817391 649559926
4519006 410772613
74521477 274584126
256535565 899389890
1 6 511428966 602601933
1 1 69986642 201421232
2 3 636443425 4 625975977
1 6 235225515 405336399
2 3 866680458 3 701821857
1 6 180606048 900533151
1 6 612564160 720179605

예제 출력 4

10467449
164858601