Có một hàng bò, ban đầu (tức tại thời điểm \(t=0\)) chỉ gồm chú bò \(0\) ở vị trí \(0\) (ở đây, một chú bò ở vị trí \(k\) nếu có \(k\) chú bò đứng trước nó). Tại thời điểm \(t\), với \(t=1,2,3,\dots\), chú bò ở vị trí \(0\) di chuyển đến vị trí \(\lfloor t/2\rfloor\), mỗi chú bò ở các vị trí \(1\dots \lfloor t/2\rfloor\) tiến lên trước một vị trí, và chú bò \(t\) gia nhập ở cuối hàng (vị trí \(t\)).

Hãy trả lời \(Q\) (\(1\le Q\le 10^5\)) truy vấn độc lập, mỗi truy vấn có dạng sau:

• Trong số các chú bò \(l_1\dots r_1\), có bao nhiêu chú nằm tại các vị trí \(l_2\dots r_2\) ngay sau thời điểm \(t\)? (\(0\le l_1\le r_1\le t\), \(0\le l_2\le r_2\le t\), \(t\le 10^{18}\))

Dữ liệu vào

Dòng đầu tiên chứa \(Q\), là số truy vấn.

\(Q\) dòng tiếp theo, mỗi dòng chứa năm số nguyên mô tả một truy vấn theo dạng "\(l_1\) \(r_1\) \(l_2\) \(r_2\) \(t\)".

Dữ liệu ra

In đáp án của mỗi truy vấn trên một dòng riêng.

Ví dụ

4
0 9 0 9 9
3 5 4 5 9
4 5 3 5 9
1 1 3 3 9

10
2
1
1

t = 0 | 0
t = 1 | 0 1
t = 2 | 1 0 2
t = 3 | 0 1 2 3
t = 4 | 1 2 0 3 4
t = 5 | 2 0 1 3 4 5
t = 6 | 0 1 3 2 4 5 6
t = 7 | 1 3 2 0 4 5 6 7
t = 8 | 3 2 0 4 1 5 6 7 8
t = 9 | 2 0 4 1 3 5 6 7 8 9

1
0 1000000000000000000 0 1000000000000000000 1000000000000000000

1000000000000000001

Phân nhóm

• Test 3: \(Q\le 1000\), \(t\le 100\).
• Các test 4–7: \(l_1=r_1\) đối với mọi truy vấn.
• Các test 8–14: \(r_1\leq 2\cdot l_1\) đối với mọi truy vấn.
• Các test 15–21: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 First Contest, Platinum Division — "Lineup Counting Queries". Tác giả: Agastya Goel và Benjamin Qi. https://usaco.org/index.php?page=viewproblem2&cpid=1549