Cho dãy số nguyên dương thỏa mãn .
Từ dãy số trên ta xây dựng một cây có đỉnh bao gồm mức với số đỉnh lần lượt là theo cách sau:
- Ở mức thứ có các đỉnh được gán nhãn ;
- Trừ mức , ở mỗi mức, đỉnh có nhãn có nút con, các đỉnh còn lại chỉ có nút con.
Một cây được xây dựng từ dãy
Có truy vấn, mỗi truy vấn có dạng “Nút cha lớn nhất của và là nút nào?” Tức là ta cần tìm đỉnh có nhãn lớn nhất và là nút cha chung của và .
Dữ liệu vào:
- Dòng đầu chứa ba số nguyên là số phần tử của dãy, số truy vấn và tham số để xác định nhãn của các đỉnh trong các quy vấn;
- Dòng thứ hai chứa phần tử của dãy ;
- dòng tiếp theo, dòng thứ chứa hai số được sử dụng để xác định nhãn của truy vấn thứ .
Gọi là đáp án của truy vấn thứ . Khi đó, nhãn của truy vấn thứ được xác định như sau:
ở đây là phép chia lấy phần dư.
Lưu ý: Khi thì .
Dữ liệu ra:
- Ghi ra dòng, dòng thứ là đỉnh có nhãn lớn nhất là cha chung của và .
Ví dụ:
Dữ liệu vào:
3 5 0
1 2 6
7 10
8 5
6 2
9 10
2 3
Dữ liệu ra:
Dữ liệu vào:
3 5 1
1 2 6
7 10
8 5
6 2
9 10
2 3
Dữ liệu ra:
Giải thích:
Trong cả hai test ví dụ thì cây được cho bởi hình trên. Đối với test ví dụ thứ ta có:
- , cha chung là ;
- , cha chung là ;
- , cha chung là ;
- , cha chung là ;
- , cha chung là .
Giới hạn:
- Subtask số điểm có ;
- Subtask số điểm khác có ;
- Subtask số điểm khác có ;
- Subtask số điểm còn lại có .
