Dũng sĩ Mofk đang trên con đường hành đạo của mình. Một ngày nọ, anh tới một khu vực với kích thước ~n*m~, con quái vật trên ô ~(i,j)~ có sức mạnh ~h_{i,j}~.

Nếu đang có sức mạnh ~s~, dũng sĩ Mofk có thể tiêu diệt các con quái vật có sức mạnh ~x~ thỏa mãn ~x < s~. Sau khi tiêu diệt con quái vật này, Mofk có thể đi vào ô chứa quái vật đó, đồng thời sức mạnh của anh sẽ cộng thêm ~x~. Ngược lại, nếu không thể tiêu diệt quái vật, anh sẽ không thể đi vào ô chứa nó.

Hãy tính sức mạnh nhỏ nhất ban đầu của dũng sĩ Mofk để anh có thể xuất phát từ ô ~(1,1)~, chỉ đi sang phải hoặc xuống dưới và đến được ô ~(n,m)~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~ ~(1 \le n,m \le 1000)~.

• Từ dòng ~2~ tới ~n+1~, mỗi dòng gồm ~m~ số nguyên dương mô tả bảng ~h_{i,j}~ ~(1 \le h_{i,j} \le 10^9)~.

Output

• Gồm một dòng in ra sức mạnh ~s~ nhỏ nhất ban đầu của dũng sĩ Mofk để thỏa mãn yêu cầu đề bài.

Scoring

• Có ~20\%~ số test thỏa mãn ~n = 1~.

• Có ~30\%~ số test thỏa mãn ~1 \le n,m \le 100~ và đáp án luôn không vượt quá ~100~.

• Có ~50\%~ số test không có ràng buộc gì thêm.

Sample Input 1

2 2
1 2
3 4

Sample Output 1

2

Notes

Ban đầu dũng sĩ Mofk có sức mạnh là ~2~.

Khi đi đến ô ~(1, 1)~, dũng sĩ tiêu diệt con quái vật ở đây và sức mạnh trở thành ~3~.

Khi đi đến ô ~(1, 2)~, dũng sĩ tiêu diệt con quái vật ở đây và sức mạnh trở thành ~5~.

Khi đi đến ô ~(2, 2)~, dũng sĩ tiêu diệt con quái vật ở đây và sức mạnh trở thành ~9~.

Mofk đang rất rảnh rỗi nên quyết định nghịch Robot. Nhà của Mofk được xem là một mặt phẳng ~Oxy~ và con Robot của Mofk ban đầu đang đứng ở điểm ~(0, 0)~.

Mofk có một xâu ký tự ~S~ độ dài ~n~ gồm các kí tự ~L, R, U, D~ là dòng lệnh được truyền vào Robot khiến Robot thực hiện các thao tác lần lượt từ trái qua phải. Cụ thể, nếu tới thao tác thứ ~i~ và vị trí hiện tại của Robot là ~(x,y)~:

• ~S_i = L~: Robot sẽ di chuyển sang trái, đến điểm ~(x - 1, y)~

• ~S_i = R~: Robot sẽ di chuyển sang phải, đến điểm ~(x + 1, y)~

• ~S_i = U~: Robot sẽ di chuyển lên trên, đến điểm ~(x, y + 1)~

• ~S_i = D~: Robot sẽ di chuyển xuống dưới, đến điểm ~(x, y - 1)~

Ban đầu, tất cả các điểm trên mặt phẳng đều được tô màu trắng. Mỗi lần Robot đứng ở bất kì điểm nào thì nó sẽ bị vấy bẩn thành màu đen (kể cả điểm ~(0, 0)~ ban đầu).

Vì thấy chưa đủ thỏa mãn, Mofk quyết định thêm một thao tác bất kì vào xâu ~S~ sao cho Robot có thể vấy bẩn nhiều điểm nhất. Hãy giúp Mofk thỏa mãn thú tính của mình.

Input

• Dòng đầu tiên chứa 1 số nguyên dương ~n~, độ dài của xâu ~S~ ~(1\le n \le 2 \times 10^5)~

• Dòng thứ hai chứa xâu ~S~ gồm ~n~ kí tự ~L,R,U,D~.

Output

• Một số nguyên duy nhất là số điểm nhiều nhất bị vấy bẩn.

Scoring

• ~50\%~ số test có ~n \le 1000~.

• ~50\%~ số test còn lại không có điều kiện gì thêm.

Sample Input 1

3
LRL

Sample Output 1

4

Notes

Mofk có thể lựa chọn thêm kí tự ~U~ vào sau kí tự thứ nhất, khi đó xâu ~S~ trở thành ~LURL~

Xuất phát từ ô ~(0, 0)~, Mofk sẽ đi qua các ô ~(-1, 0)~, ~(-1, 1)~, ~(0, 1)~, ~(-1, 1)~. Tổng cộng có ~4~ điểm phân biệt trên bị Mofk vấy bẩn là ~(0, 0)~, ~(-1, 0)~, ~(-1, 1)~, ~(0, 1)~.

Hôm nay, trong giờ học thủ công, Mofk được học cách gấp máy bay phản lực bằng giấy nhưng loay hoay mãi không gấp được nên Mofk cũng đành bó tay. Trong lúc chờ sự trợ giúp từ thầy giáo, vì chán quá nên Mofk đã đặt chồng các tờ giấy có kích thước khác nhau. Chợt có một bài toán hay nảy ra trong đầu khiến Mofk vô cùng thích thú:

Cho ~n~ tờ giấy hình chữ nhật, tờ giấy thứ ~i~ có góc trái dưới ở ~(0, 0)~ và góc phải trên ở ~(x_i, y_i)~. Hãy tìm diện tích phần bị phủ bởi đúng ~k~ tờ giấy.

Thầy giáo đã đến để giúp Mofk gấp máy bay, trong thời gian đó bạn hãy thử giải bài toán Mofk vừa nghĩ ra nhé!

Input

• Dòng đầu gồm ~2~ số nguyên dương ~n~ và ~k~ ~(1 \le k \le n \le 10^6)~.

• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ gồm 2 số nguyên dương ~x_i~, ~y_i~ ~(1 \le x_i, y_i \le 10^6)~, là tọa độ góc phải trên của tờ giấy thứ ~i~.

Output

Gồm một số nguyên dương duy nhất là diện tích phần bị phủ bởi đúng ~k~ tờ giấy hình chữ nhật

Scoring

• ~20\%~ số test có ~x_i \le x_{i+1}, y_i \le y_{i+1}~ ~\forall~ ~1 \le i \le n - 1~.

• ~30\%~ số test khác có ~n \le 1000~.

• ~50\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

5 2
1 4
2 3
3 5
2 7
4 1

Sample Output 1

4

Notes

*Giải thích test ví du: *

• Một phần có diện tích là ~3~ được phủ bởi đúng 2 tờ giấy có tọa độ phải trên là ~(2;7), (3;5)~.

• Một phần có diện tích là ~1~ được phủ bởi đúng 2 tờ giấy có tọa độ phải trên là ~(3;5), (4;1)~

Ban tổ chức Mofk Cup quyết định tổ chức ~1~ buổi văn nghệ. Ở một tiết mục, họ cử ra ~n~ cặp bạn, cặp bạn đồng hành thứ ~i~ có chiều cao ~i~. Tiết mục này ~2n~ người trên sẽ xếp thành ~1~ hàng ngang. Sẽ có một số vị trí quan trọng, được gọi là "spotlight", được đánh số ~1~, và các vị trí còn lại được đánh số ~0~.

Hàng ~2n~ người trên sẽ được gọi là đẹp nếu ở mỗi vị trí spotlight, người đứng ở đó có thể nhìn thấy bạn đồng hành cùng cặp của mình, và những vị trí không phải spotlight thì không thể nhìn thấy bạn đồng hành cùng cặp của mình. ~2~ người trong cùng ~1~ cặp đôi được gọi là nhìn thấy nhau nếu tất cả mọi người ở các vị trí giữa họ đều có chiều cao thấp hơn họ. Nói cách khác, nếu ~2~ người trong cùng ~1~ cặp đôi đứng ở vị trí ~L~ và ~R~, thì: ~h_L= h_R > max(h_{L+1},h_{L+2},...,h_{R-1})~.

Hãy giúp ban tổ chức xem có cách để xếp ~2n~ người trên vào hàng sao cho hàng đó được coi là đẹp hay không. Nếu có, hãy in ra ~1~ cách bất kì.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ là số lượng cặp đôi ~(1 \leq n \leq 5\times10^5)~.

Dòng thứ hai là một chuỗi ký tự độ dài ~2n~ chỉ bao gồm 2 loại ký tự '0' và '1'. Người ở vị trí ~i~ sẽ nhìn thấy bạn đồng hành của mình khi ký tự thứ ~i~ là '1'.

Output

Ở dòng đầu tiên, nếu có tồn tại kết quả thì in ra "YES", không thì "NO" (in ra không có dấu nháy đôi và không quan trọng in hoa).

Nếu có tồn tại kết quả thì in ra dòng thứ 2 bao gồm ~2n~ số nguyên dương. Số thứ ~i~ là chiều cao của người thứ ~i~ và thỏa mãn yêu cầu đề bài.

Scoring

• ~20\%~ số test có: ~0 < n \le 20~.

• ~30\%~ số test khác có ~0 < n \le 3000~.

• ~50\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

5
1000100000

Sample Output 1

YES
5 4 3 2 5 1 4 3 2 1

Mofk mới được mẹ mua cho một bộ đồ chơi biến đổi các xâu nhị phân. Ở vị trí thứ ~i~ trên bộ đồ chơi được ghi một giá trị ~a_i~. Khi đưa một xâu nhị phân ~s~ độ dài ~n~ vào vị trí ~i~ của bộ đồ chơi, Mofk sẽ nhận lại được một xâu ~s' = s \oplus (s >> a_i)~. Trong đó ~>>~ là phép cyclic right shift, mỗi lần thực hiện phép biến đổi này, ta di chuyển kí tự cuối cùng của ~s~ lên đầu xâu và tất cả các kí tự còn lại dịch sang phải ~1~ đơn vị (~abcde~ ~>>~ ~2~ = ~deabc~), và ~\oplus~ là phép toán XOR.

Rất hào hứng với bộ đồ chơi mới, Mofk đem nó đi khoe với tất cả bạn bè của mình, và ngay lập tức đã rủ được ~q~ người bạn đến thử bộ đồ chơi mới của mình. Người bạn thứ ~i~ đem theo một xâu nhị phân ~s_i~ độ dài ~n~ và muốn dùng xâu của mình thử lần lượt trên các vị trí từ ~l~ đến ~r~. Để tăng sự vui vẻ, Mofk cùng các người bạn muốn đoán xem sau khi chơi xong, xâu kết quả mà người bạn thứ ~i~ nhận được sẽ như thế nào, ai đoán trúng nhiều hơn sẽ thắng.

Hòa cùng niềm vui đó, bạn hãy thử sức mình xem có thể đánh bại được Mofk không nhé.

Input

Dòng đầu tiên chứa ba số nguyên ~n~, ~m~, ~q~ lần lượt là độ dài của các xâu nhị phân, kích thước của bộ đồ chơi và số người bạn của Mofk ~(1 \leq n \leq 16, 1 \leq m \leq 10^4, 1 \leq q \leq 10^6)~.

Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, ..., a_m~ mô tả các giá trị của từng vị trí trên bộ đồ chơi ~(0 \leq a_i < n)~.

~Q~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~x_i, l_i, r_i~ với ~x_i~ là một số nguyên ~n~ bit mô tả xâu nhị phân người bạn thứ ~i~ đem theo, ~l_i~ và ~r_i~ mô tả các vị trí mà người bạn này sẽ chơi ~(0 \leq x_i < 2^n, 1 \leq l_i \leq r_i \leq m)~.

Output

Gồm ~q~ dòng, dòng thứ ~i~ gồm một số nguyên ~n~ bit mô tả xâu nhị phân mà bạn đoán người bạn thứ ~i~ sẽ nhận được.

Scoring

• ~20\%~ số test có ~n \leq 10, m \leq 1000, q \leq 1000~.

• ~30\%~ số test khác có ~n \leq 10, m \leq 1000, q \leq 10^5~.

• ~30\%~ số test khác so ~n \leq 16, m \leq 10^4, q \leq 10^5~.

• ~20\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

4 3 3
2 1 3
3 1 1
5 1 2
7 1 3

Sample Output 1

15
0
0

Notes

Người bạn thứ nhất mang tới xâu ~s_1 = 0011~, sau khi chơi vị trí thứ nhất, xâu của người bạn này trở thành ~s_1' = 0011 \oplus 1100 = 1111~. Xâu này có giá trị ~15~ trong biểu diễn thập phân.

Người bạn thứ hai mang tới xâu ~s_2 = 0101~, sau khi chơi vị trí thứ nhất, xâu của người bạn này trở thành ~s_2' = 0101 \oplus 0101 = 0000~. Sau khi chơi vị trí thứ hai, xâu của người bạn này trở thành ~s_2'' = 0000 \oplus 0000 = 0000~. Xâu này có giá trị ~0~ trong biểu diễn thập phân.

Cho một bảng ~n \times m~ (~n, m~ lẻ) được lát bởi các viên gạch ~2 \times 1~ nằm ngang hoặc dọc, trừ đúng 1 ô. Dưới một số ô có chứa kho báu. MofK được phép thực hiện 1 trong 2 thao tác sau:

- Đẩy một trong những viên gạch ở cạnh ô trống vào ô trống. MofK không được phép thay đổi hướng của viên gạch. Thao tác này tốn 1 giây.

- Lấy kho báu nằm dưới ô trống (nếu có). Thao tác này tốn 0 giây.

Hỏi MofK có thể lấy được nhiều nhất bao nhiêu kho báu, và thời gian ngắn nhất để MofK lấy được những kho báu đó là bao lâu?

Input

- Dòng đầu tiên gồm hai số nguyên dương lẻ ~n, m~ ~(n * m \leq 5\cdot 10^5)~

- ~n~ dòng tiếp theo là xâu gồm ~m~ kí tự trong bảng chữ cái tiếng Anh in thường tượng trưng cho bảng viên gạch, một viên gạch là hai kí tự giống nhau kề nhau. Bộ test đảm bảo với mỗi một ô chỉ có đúng một ô kề cạnh có kí tự giống nhau (trừ ô trống).

- ~n~ dòng tiếp theo là xâu nhị phân gồm ~m~ kí tự cho biết vị trí các kho báu, các ô ~1~ là có kho báu và ngược lại.

Output

- In ra hai số nguyên thoả mãn yêu cầu đề bài

Scoring

• ~20\%~ số test có ~n = 1~.

• ~80\%~ số test còn lại không có ràng buộc gì thêm.

Với mỗi test, bài làm của thí sinh sẽ được 50% số điểm nếu tìm được số lượng kho báu lớn nhất tìm được.

Sample Input 1

3 5
aa.zz
lmall
lmaoo
10100
00100
00101

Sample Output 1

4 4

Sample Input 2

3 3
llo
o.o
oll
111
101
111

Sample Output 2

0 0