Beaverland có \(N\) thành phố, được đánh số từ \(1\) đến \(N\), và \(N-1\) con đường nối các thành phố. Đường thứ \(i\) nối thành phố \(i\) với thành phố \(i+1\) theo cả hai chiều.

Ở Beaverland, đơn vị thời gian là Byou. Mỗi ngày dài \(1\,000\,000\,000\) Byou. Thời điểm cách đầu ngày \(x\) Byou, với \(0 \le x < 1\,000\,000\,000\), được gọi là thời điểm \(x\). Đi qua bất kỳ con đường nào cũng mất \(1\) Byou. Mỗi ngày, đường thứ \(i\) chỉ có thể được đi qua trong khoảng từ thời điểm \(L_i\) đến thời điểm \(R_i\). Cụ thể, để đi qua đường này, phải rời thành phố \(i\) hoặc \(i+1\) tại thời điểm \(x\) thỏa mãn \(L_i \le x \le R_i-1\) và đến thành phố còn lại tại thời điểm \(x+1\).

Bitaro vốn là một chú hải ly bình thường sống ở Beaverland. Tuy nhiên, trong lúc tìm cách đối phó với việc đi muộn, cậu đã có được khả năng quay ngược thời gian. Mỗi lần sử dụng khả năng này, cậu quay lại thời điểm cách đó \(1\) Byou. Cậu không thể quay về ngày trước: nếu dùng khả năng tại một thời điểm từ \(0\) đến trước \(1\), cậu sẽ quay về thời điểm \(0\) của ngày đó. Bitaro chỉ có thể dùng khả năng khi đang ở một thành phố. Vị trí của cậu không thay đổi khi sử dụng khả năng.

Mỗi lần quay ngược thời gian đều khiến Bitaro mệt mỏi. Để tìm cách di chuyển mà sử dụng khả năng ít lần hơn, cậu thực hiện một thí nghiệm tưởng tượng gồm \(Q\) bước. Ở bước thứ \(j\), cậu thực hiện một trong hai việc:

• Thay đổi khoảng thời gian có thể đi qua đường thứ \(P_j\). Sau thay đổi, đường này chỉ có thể được đi qua từ thời điểm \(S_j\) đến thời điểm \(E_j\).
• Giả sử Bitaro đang ở thành phố \(A_j\) tại thời điểm \(B_j\). Tính số lần sử dụng khả năng ít nhất để cậu có mặt ở thành phố \(C_j\) tại thời điểm \(D_j\) trong cùng ngày.

Hãy tính kết quả của thí nghiệm này.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả các giá trị đều là số nguyên.

N Q
L_1 R_1
...
L_{N-1} R_{N-1}
Truy_van_1
...
Truy_van_Q

Mỗi truy vấn gồm bốn hoặc năm số nguyên, ngăn cách nhau bằng dấu cách. Gọi số đầu tiên là \(T_j\):

• Nếu \(T_j=1\), truy vấn có dạng 1 P_j S_j E_j. Ở bước này, khoảng thời gian có thể đi qua đường thứ \(P_j\) được thay đổi thành khoảng từ \(S_j\) đến \(E_j\); tức là thời điểm khởi hành \(x\) phải thỏa mãn \(S_j \le x \le E_j-1\).
• Nếu \(T_j=2\), truy vấn có dạng 2 A_j B_j C_j D_j. Hãy tính số lần sử dụng khả năng ít nhất để Bitaro có mặt ở thành phố \(C_j\) tại thời điểm \(D_j\) trong ngày đó, giả sử cậu bắt đầu ở thành phố \(A_j\) tại thời điểm \(B_j\).

Dữ liệu ra

Với mỗi truy vấn có \(T_j=2\), theo đúng thứ tự xuất hiện, ghi một dòng chứa số lần sử dụng khả năng ít nhất ra đầu ra chuẩn.

Ràng buộc

• \(1 \le N \le 300\,000\).
• \(1 \le Q \le 300\,000\).
• \(0 \le L_i < R_i \le 999\,999\,999\) với \(1 \le i \le N-1\).
• \(1 \le T_j \le 2\) với \(1 \le j \le Q\).
• Với mọi truy vấn loại \(1\): \(1 \le P_j \le N-1\) và \(0 \le S_j < E_j \le 999\,999\,999\).
• Với mọi truy vấn loại \(2\): \(1 \le A_j,C_j \le N\) và \(0 \le B_j,D_j \le 999\,999\,999\).

Phân nhóm

1. \(4\) điểm: \(N \le 1\,000\) và \(Q \le 1\,000\).
2. \(30\) điểm: \(T_j=2\) với mọi \(1 \le j \le Q\); không có truy vấn thay đổi đường.
3. \(66\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

2
4

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

4
3
2
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

145611455
0
447180143
0
207252171
0
0

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

10467449
164858601

Nguồn

JOI 2018/2019, trại huấn luyện mùa xuân, ngày thi thứ 3 (22/03/2019). Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản. Trang công bố cấp phép nội dung theo CC BY-SA 4.0; bản dịch giữ cùng giấy phép.