Cho dãy số gồm N số nguyên dương đánh số vị trí từ 1 tới N. Tất cả các phần tử có giá trị khác nhau và có giá trị trong đoạn từ 1 tới N. Chọn một dãy con liên tiếp, và thực hiện các phép quay. Một phép quay trái là chuyển 1 phần tử ở đầu dãy con xuống cuối dãy con. Một phép quay phải là chuyển 1 phần tử ở cuối dãy con lên đầu dãy con. Ví dụ: Nếu dãy con được chọn là (5,1,8,3), khi thực hiện một phép quay trái ta được dãy (1,8,3,5), tương tự, thực hiện một phép quay phải ta được dãy (3,5,1,8).
Có 3 loại truy vấn:
|
Loại
|
Thực hiện
|
Kí hiệu
|
|
1
|
Chọn dãy con liên tiếp từ vị trí a tới b và quay trái k lần
|
L a b k
|
|
2
|
Chọn dãy con liên tiếp từ vị trí a tới b và quay phải k lần
|
R a b k
|
|
3
|
Trả về giá trị phần tử ở vị trí x của dãy.
|
P x
|
Ràng buộc:
- Loại 1 và 2: 1 ≤ a < b ≤ N, và 1 ≤ k < b – a + 1.
- Loại 3: 1 ≤ x ≤ N.
Dữ liệu:
- Dòng 1: Hai số nguyên N (2 ≤ N ≤ 100 000) và Q (1 ≤ Q ≤ 100 000) cách nhau bởi dấu cách, lần lượt là số phần tử của dãy và số truy vấn.
- Dòng 2: N số nguyên dương cách nhau bởi dấu cách, là dãy số ban đầu.
- Q dòng sau: Mỗi dòng là một truy vấn mô tả như trên.
Kết quả:
- Với mỗi truy vấn loại 3, trả về giá trị phần tử ở vị trí x của dãy trên một dòng.
Thang điểm:
- 10% bộ test: N, Q ≤ 1000 : tất cả truy vấn loại 3 ở sau tất cả truy vấn loại 1 và 2.
- 10% bộ test: N ≤ 100 000, Q ≤ 1000 : tất cả truy vấn loại 3 ở sau tất cả truy vấn loại 1 và 2.
- 50% bộ test: N ≤ 100 000, Q ≤ 100 000:tất cả truy vấn loại 3 ở sau tất cả truy vấn loại 1 và 2
- 30% bộ test còn lại: N ≤ 100 000, Q ≤ 100 000.
Ví dụ:
|
INPUT
|
OUTPUT
|
|
7 5
7 5 3 1 4 2 6
L 1 3 2
R 2 4 1
P 1
P 4
P 7
|
3
5
6
|
Giải thích:
Dãy ban đầu: 7 5 3 1 4 2 6
L 1 3 2 -> 3 7 5 1 4 2 6
R 2 4 1 -> 3 1 7 5 4 2 6
P 1 -> Phần tử ở vị trí 1 là: 3
P 4 -> Phần tử ở vị trí 4 là: 5
P 7 -> Phần tử ở vị trí 7 là: 6
|
INPUT
|
OUTPUT
|
|
5 5
3 5 4 2 1
R 3 5 1
R 1 4 1
P 1
R 1 5 4
P 1
|
4
3
|
Giải thích:
Dãy ban đầu: 3 5 4 2 1
R 3 5 1 -> 3 5 1 4 2
R 1 4 1 -> 4 3 5 1 2
P 1 -> Phần tử ở vị trí 1 là : 4
R 1 5 4 -> 3 5 1 2 4
P 1 -> Phần tử ở vị trí 1 là: 3
