Trên đường phố sẽ được xây tòa nhà nằm cạnh nhau, nhìn từ trái qua phải, độ cao dự kiến của chúng lần lượt là . Ban đầu, độ cao của các tòa nhà bằng .
Giám đốc là tổng phụ trách. Ở mỗi giai đoạn, giám đốc chọn một đoạn để làm việc. Trong giai đoạn này, độ cao các tòa nhà sẽ tăng lên . Khi với mọi thì dự án sẽ dừng.
Kế hoạch xây dựng luôn thay đổi, có sự kiện thuộc hai kiểu sau:
thay đổi thành với mọi
, giả sử , hỏi xem cần tối thiểu bao nhiêu giai đoạn để dự án hoàn thành.
Dữ liệu vào:
Dòng đầu ghi số test . Ở mỗi test:
dòng đầu ghi hai số và là số tòa nhà và số sự kiện.
Dòng thứ hai ghi số nguyên
Sau đó là dòng, mỗi dòng ghi sự kiện như mô tả ở trên.
Đảm bảo và
Dữ liệu ra:
Với mỗi truy vấn, in ra trên một dòng kết quả cần tìm
Ví dụ:
Dữ liệu vào:
1
5 4
1 3 1 4 5
2 1 5
1 3 4 2
2 2 4
2 1 5
Dữ liệu ra:
7
6
6
Giới hạn:
Subtask : số test có
Subtask : số test khác có
Subtask : số test còn lại không có giới hạn gì thêm.
