Có một hàng gồm các con bò, ban đầu (tức là tại thời điểm \(t=0\)) chỉ có bò \(0\) ở vị trí \(0\) (ở đây, một con bò ở vị trí \(k\) nếu có \(k\) con bò đứng trước nó). Tại thời điểm \(t\) với \(t=1,2,3,\dots\), con bò ở vị trí \(0\) di chuyển đến vị trí \(\lfloor t/2\rfloor\), mỗi con bò ở các vị trí \(1\dots \lfloor t/2\rfloor\) tiến lên trước một vị trí, và bò \(t\) gia nhập hàng ở 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 thuộc một trong các loại sau:

1. Ngay sau thời điểm \(t\), bò \(c\) ở vị trí nào (\(0\le c\le t\le 10^{18}\))?
2. Ngay sau thời điểm \(t\), con bò nào ở vị trí \(x\) (\(0\le x\le t\le 10^{18}\))?

Dữ liệu vào

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

\(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên mô tả một truy vấn, có dạng 1 c t hoặc 2 x 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ụ

2
1 4 9
2 2 9

2
4

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

22
1 0 9
1 1 9
1 2 9
1 3 9
1 4 9
1 5 9
1 6 9
1 7 9
1 8 9
1 9 9
2 0 9
2 1 9
2 2 9
2 3 9
2 4 9
2 5 9
2 6 9
2 7 9
2 8 9
2 9 9
1 0 1000000000000000000
2 0 1000000000000000000

1
3
0
4
2
5
6
7
8
9
2
0
4
1
3
5
6
7
8
9
483992463350322770
148148148148148148

Phân nhóm

• Input 3: \(Q\le 1000, t\le 100\).
• Input 4: \(t\le 5000\).
• Inputs 5–8: Tất cả các truy vấn đều thuộc loại 1.
• Inputs 9–12: Tất cả các truy vấn đều thuộc loại 2.

Nguồn

USACO 2026 First Contest, Silver — bài gốc tiếng Anh “Lineup Queries”, tác giả Agastya Goel: https://usaco.org/index.php?page=viewproblem2&cpid=1542