Lê rất thích trò chơi domino từ khi còn bé. Lấy cảm hứng từ trò chơi domino, gần đây Lê sáng tạo ra trò chơi mới có tên là numino gồm ~n~ quân. Mỗi quân numino là một hình chữ nhật được chia làm hai nửa trên cùng một mặt, trên mỗi nửa có ghi một số nguyên không âm. Các con số trên các nửa của các quân numino có thể khác nhau, nhưng tổng hai số trên hai nửa của mỗi quân numino đều bằng một giá trị cố định ~s~.

Lê đặt ~n~ quân numino lên bàn, xếp chúng thành một dãy ngang, mỗi quân đều xếp theo chiều dọc vào dây và đánh số các quân lần lượt từ ~1~ đến ~n~ theo thứ tự từ trái qua phải. Như thế, mỗi quân numino trong dãy sẽ có một nửa ở trên và một nửa ở dưới. Ban đầu, ở quân numino thứ ~i~, nửa trên ghi số ~a_i~ và nửa dưới ghi số ~(s - a_i)~. Lê lần lượt thực hiện ~q~ thao tác với các quân numino của mình, mỗi thao tác thuộc một trong ba loại sau:

1. ~> l \space r \space b~: Lê xét tất cả các quân numino có vị trí từ ~l~ đến ~r~, nếu con số ở nửa trên của một quân numino nào đó có giá trị lớn hơn ~b~ thì Lê sẽ đảo hai nửa bằng cách xoay ngược quân numino này.

2. ~< l \space r \space b~: Lê xét tất cả các quân numino có vị trí từ ~l~ đến ~r~, nếu con số ở nửa trên của một quân numino nào đó có giá trị nhỏ hơn ~b~ thì Lê sẽ đảo hai nửa bằng cách xoay ngược quân numino này.

3. ~? \space p~: Lê ghi ra vở con số ở nửa trên của quân numino thứ ~p~ tại thời điểm đang xét dãy.

Khi Lê xoay ngược một quân numino, hai nửa của quân numino sẽ đổi chỗ cho nhau. Nói cách khác, giả sử một quân có số ~x~ ở nửa trên và số ~y~ ở nửa dưới, thì sau khi xoay ngược quân numino này, con số ở nửa trên sẽ là ~y~ và con số ở nửa dưới là ~x~. Lưu ý rằng, với mỗi thao tác loại ~1~ và ~2~, Lê chỉ có thể xoay ngược các quân numino chứ không thay đổi thứ tự vị trí của chúng ở dãy xuất phát.

Yêu cầu: Hãy viết chương trình giúp Lê ghi lại con số ở nửa trên các quân numino trong các thao tác 3.

Input

Dòng đầu chứa ba số nguyên dương ~n, s, q \space (n, q \le 5 \cdot 10^5, s \le 10^7)~ lần lượt là số quân numino, tổng giá trị hai số trên mỗi quân numino và số thao tác Lê sẽ thực hiện.

Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, ..., a_n (a_i \le s)~, với ~a_i~ là số ở nửa trên của quân numino thứ ~i \space (1 \le i \le n)~.

Mỗi dòng trong số ~q~ dòng cuối cùng mô tả một thao tác thuộc một trong ba loại ở trên:

1. ~> l \space r \space b~: Loại thứ nhất gồm một kí tự ~>~, tiếp theo là dấu cách và ~3~ số nguyên dương ~l \space r \space b~

2. ~< l \space r \space b~: Loại thứ hai gồm một kí tự ~<~, tiếp theo là dấu cách và ~3~ số nguyên dương ~l \space r \space b~

3. ~? \space p~: Loại thứ ba gồm một kí tự ~?~, tiếp theo là dấu cách và một số nguyên dương ~p~ ~(1 \le l \le r \le n, 1 \le p \le n, 0 \le b \le 10^7)~.

Output

Với mỗi thao tác loại 3, ghi ra một số nguyên trên một dòng là con số tại nửa trên của quân numino ở vị trí ~p~.

Scoring

Sample Input 1

5 30 8
17 18 20 22 26
? 1
< 2 4 21
? 3
? 2
> 3 5 25
? 5
< 1 4 24
? 4

Sample Output 1

17
10
12
4
8