Giải bài trực tuyến

Bờm là một đứa trẻ có trí nhớ siêu việt. Cùng một lúc, Bờm có thể nhớ một lượng lớn các thông tin. Vì thế từ lâu, Bờm đã có ý định tham gia trò chơi “Thử tài trí nhớ” trên TV. Đó là một chương trình khá được yêu thích hiên nay, ai chiến thắng sẽ được một thưởng không trên 1 tỷ đồng.

Trò chơi được thực hiện trên 1 dãy gồm N (N<=10^5) số. Dãy số chỉ được đưa ra trong 5 phút đầu tiên. Sau đó bạn phải cho biết thông tin về dãy để ghi điểm. Ghi nhớ là một việc dễ dàng đối với Bờm. Nhưng, giữa các câu hỏi dãy số bị thay đổi. Nên Bờm hay lẫn lộn khi số lượng thay đổi tăng lên quá nhiều.

Input

-          Dòng đầu tiên chứa 2 số N, M – số thay đổi và yêu cầu (M <= 10^5).

-          N dòng tiếp theo là các giá trị của dãy số - a_i (a_i <= 10^9).

-          M dòng tiếp theo là các yêu cầu có dạng:

• 1 L R : Đảo ngược dãy con từ phần tử L đến R.
• 2 K : Hỏi giá trị tại vị trí thứ K trong dãy hiện tại.

Output

-          In ra kết quả tương ứng trên mỗi dòng đối với mỗi câu hỏi của trò chơi.

Example

Input:

6 4

1

2

3

4

5

6

1 1 4

1 3 5

2 5

2 6

Ouput:

2

6

Giải thích: Dãy số sau các biến đổi

(1, 2, 3, 4, 5, 6)

(4, 3, 2, 1, 5, 6)

(4, 3, 5, 1, 2, 6)