#5446. Thang máy và thang bộ (LIFTWALK)

Trong một toà nhà chọc trời hiện đại, việc di chuyển giữa các tầng là một thử thách không nhỏ. Người quản lý tòa nhà đã lắp đặt những thang máy đặc biệt tại một số tầng nhất định. Chúng hoạt động khác thường: mỗi lần sử dụng, thang máy sẽ đưa hành khách đi một quãng cố định, và công suất của nó lại tăng gấp đôi cho lần kế tiếp.

Tuy nhiên, không phải tầng nào cũng có thang máy. Nếu một người dừng lại ở một tầng không có thang máy, cách duy nhất là đi bộ xuống cầu thang một tầng, mất 1 giây. Ngược lại, nếu tầng đó có thang máy, anh ta sẽ ngay lập tức được đưa lên cao thêm nhiều tầng, theo công suất hiện tại của thang máy, cũng mất 1 giây.

Mỗi hành trình trở thành một chuỗi xen kẽ giữa việc đi bộ xuống và đi thang máy lên. Câu hỏi đặt ra: sau một khoảng thời gian xác định, người đó sẽ đứng ở tầng nào?

Dữ liệu:

• Dòng đầu tiên chứa số nguyên .

• dòng tiếp theo, dòng thứ chứa hai số nguyên , mô tả vị trí tầng và công suất ban đầu của thang máy. Các vị trí thỏa và .

• Dòng tiếp theo chứa số nguyên .

• dòng tiếp theo, dòng thứ chứa hai số nguyên , tương ứng là tầng bắt đầu và số giây hành trình.

Kết quả: In ra dòng, dòng ghi tầng cuối cùng mà người đó sẽ đứng sau đúng giây trong truy vấn thứ .

Ví dụ:

Dữ liệu:

2
1 2
4 3
7
2 1
2 2
2 3
2 4
2 5
2 6
2 7

Kết quả:

1
3
2
1
5
4
7

Dữ liệu:

3
-2 3
3 2
12 6
4
2 6
5 12
12 3
10 4

Kết quả:

0
10
16
6

Giới hạn:

• Subtask 1 ( số điểm): .

• Subtask 2 ( số điểm): .

• Subtask 3 ( số điểm): .

• Subtask 4 ( số điểm): .

• Subtask 5 ( số điểm): Không có ràng buộc bổ sung.