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

Tham gia cuộc thi "Thiết kế thuật toán nén dữ liệu", các thí sinh được Ban tổ chức yêu cầu xây dựng hàm nén dữ liệu và trả lời truy vấn như sau:

• Hàm nén dữ liệu: string zip(string x), trong đó:

  • ~x~ là một xâu nhị phân độ dài ~n~;

  • hàm cần trả về một xâu nhị phân ~y~ là xâu ~x~ sau khi nén;

• Hàm trả lời truy vấn: vector<int> answer(int n, string y), trong đó:

  • ~y~ là kết quả sau khi nén xâu ~x~ và ~n~ là độ dài xâu ~x~;

  • hàm cần trả về một dãy ~r~ có độ dài ~n~, trong đó ~r[i]~ (~0 \le i < n~) là số lượng số ~1~ nhiều nhất có thể khi chọn một xâu con gồm ~i+1~ ký tự liên tiếp của ~x~;

  • Kết quả trả về được chấp nhận nếu mọi phần tử chênh lệch không quá ~5\%~ với kết quả đúng, cụ thể, gọi ~s~ là dãy kết quả đúng thì ~\frac{|s[i]-r[i]|}{s[i]}\le 5\%~;

Input

Thí sinh cần cài đặt hai hàm đã nêu trong chương trình và cần phải khai báo thư viện bằng dòng lệnh #include "apziplib.h" ở đầu chương trình. Ngoài ra, thí sinh được phép khai báo thêm thư viện, xây dựng các hàm, sử dụng biến toàn cục khác nếu cần.

Lưu ý rằng, hàm zip và answer sẽ được gọi ở các tiến trình độc lập. Vì vậy, nếu hàm zip có sử dụng và lưu trữ dữ liệu vào các biến toàn cục, các dữ liệu này sẽ không tồn tại khi hàm answer được thực thi.

Scoring

Có tất cả ~5~ subtask. Với mỗi subtask, gọi ~Q~ là yêu cầu mức độ nén, với mỗi test trong subtask, cách tính phần trăm số điểm như sau:

• Thí sinh sẽ nhận được ~0\%~ số điểm nếu:

  • chạy sinh lỗi;

  • tương tác sai quy cách;

  • chạy quá thời gian;

  • kết quả trả về của hàm answer không được chấp nhận;

• Ngược lại, gọi ~TS~ là độ dài xâu ~y~ mà thí sinh nén từ xâu ~x~, khi đó phần trăm số điểm của test là:

  • ~0\%~ nếu ~TS>3\times Q~;

  • ~100\%~ nếu ~TS\le Q~;

  • ~100\%\times\frac{3\times Q-TS}{2\times Q}~ nếu ~Q<TS\le 3\times Q~;</p>

Với mỗi subtask, gọi ~e~ là phần trăm số điểm nhỏ nhất của một test mà thí sinh đạt được trong các test thuộc subtask, ~score~ là điểm của subtask, khi đó, điểm cho subtask được tính bằng ~e\times score~.

Lê là người thắng cuộc trong cuộc thi "Thiết kế thuật toán nén dữ liệu" và được nhận các phần thưởng của Ban tổ chức. Ban tổ chức đã chuẩn bị n món quà, các món quà được đánh số từ ~0~ đến ~n - 1~, món quà thứ ~i~ (~0 \le i < n~) có giá trị là một số nguyên dương ~v_i~ và Lê được chọn lấy một số món quà nhưng tổng giá trị các món quà không được vượt quá ~S~. Để việc chọn các món quà thêm phần thú vị, Ban tổ chức đưa ra cách thức chọn quà như sau:

• Ban tổ chức công khai giá trị của từng món quà nhưng không cho Lê biết giá trị ~S~.

• Lê được thực hiện không quá ~t~ lượt chọn quà, ở lượt thứ ~r~ (~0 \le r < t~), Lê cần đưa ra một dãy số ~p_0,p_1,\ldots,p_{n-1}~ là hoán vị của ~0, 1,\ldots,n- 1~ thể hiện thứ tự ưu tiên chọn các món quà. Khi đó, Ban tổ chức sẽ cho Lê biết số món quà mà Lê có thể nhận được nếu ưu tiên lấy các món quà theo thứ tự đó. Cụ thể, Ban tổ chức sẽ cho Lê biết giá trị ~c~ lớn nhất mà ~v_{p_0}+v_{p_1}+\ldots+v_{p_{c-1}}\le S~ hoặc thông báo ~c = 0~ nếu không lấy được món quà nào.

• Sau khi thực hiện một số lượt không vượt quá ~t~, Lê có thể dừng và được phép chọn các món quà ở một lượt nào đó mà tổng giá trị các món quà ở lượt đó là lớn nhất trong các lượt đã thực hiện.

Yêu cầu: Hãy giúp Lê đưa ra cách chọn quà sao cho tổng giá trị các món quà được nhận là lớn nhất.

Input

Thí sinh cần cài đặt hàm: void run(int n, vector<int> v, int t), trong đó:

• ~n~ là số món quà;

• ~v~ là vector chứa thông tin về giá trị các món quà với ~v[i]~ là giá trị món quà thứ ~i~;

• ~t~ là số lượt cho phép;

Hàm trên có thể gọi đến hàm sau: int select(vector<int> p), trong đó:

• ~p~ là một hoán vị của dãy ~0,1,\ldots,n-1~;

• hàm này trả về số lượng món quà lấy được nếu ưu tiên lấy các món quà theo thứ tự mô tả bởi hoán vị ~p~;

• hàm này không được gọi quá ~t~ lần.

Trong chương trình thí sinh cần phải khai báo thư viện bằng dòng lệnh #include "bonuslib.h" ở đầu chương trình. Ngoài ra, thí sinh được phép khai báo thêm thư viện, xây dựng các hàm, sử dụng biến toàn cục khác nếu cần.

Scoring

Có tất cả ~6~ subtask. Với mỗi test trong mỗi subtask, luôn tồn tại phương án chọn để tổng giá trị bằng đúng và phần trăm số điểm cho mỗi test được tính như sau:

• Thí sinh sẽ nhận được ~0\%~ số điểm nếu:

  • chạy sinh lỗi;

  • tương tác sai quy cách;

  • chạy quá thời gian;

  • hàm select được gọi quá ~t~ lần;

• Ngược lại, gọi ~TS~ là tổng giá trị của các món quà trong cách chọn của thí sinh, ~GK~ là tổng giá trị của các món quà trong cách chọn của giám khảo, khi đó phần trăm số điểm của test là:

  • ~0\%~ nếu ~Q>1~;

  • ~100\%~ nếu ~Q<0~;

  • ~100\%\times (-\log\_{10}(0.9\times Q+0.1))~ nếu ~0\le Q\le 1~;

  với ~Q=2\times n\times \dfrac{GK-TS}{GK}~.

Với mỗi subtask, gọi ~e~ là phần trăm số điểm nhỏ nhất của một test mà thí sinh đạt được trong các test thuộc subtask, ~score~ là điểm của subtask, khi đó, điểm cho subtask được tính bằng ~e\times score~.

Notes

Giả sử có ~4~ món đồ với giá trị tương ứng là ~\{9,3,1,5\}~ và ~t=3~, ~S=8~, hàm run sẽ được gọi với giá trị các tham số tương ứng là run(4,9,3,1,5,3). Dưới đây là một ví dụ cách gọi lần lượt các hàm select: