Những người làm vườn có kinh nghiệm nhận thấy rằng nếu một quả cà chua chín đỏ (R) được đặt giữa những quả cà chua xanh (G) đã hái thì những quả cà chua xanh lân cận sẽ chín sau đúng một ngày. Có ~n~ quả cà chua được xếp cạnh nhau thành một hàng, đánh số từ ~1~ đến ~n~. Ba trong số những quả cà chua này đã chín, vị trí của chúng trong hàng là ~m_1, m_2, m_3~.

Yêu cầu

Hãy tìm số cà chua xanh còn lại sau ~d~ ngày.

Dữ liệu đầu vào

Gồm một dòng chứa năm số nguyên ~n, m_1, m_2, m_3~ và ~d~ ~(4 \le n \le 10^{16};\ 1 \le m_i \le n;\ i = 1, 2, 3;\ 1 \le d \le 10^{16})~. Các số cách nhau dấu cách.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số cà chua xanh còn lại sau ~d~ ngày.

Ràng buộc dữ liệu

• Có 50% số điểm có ~n \le 10^{9}~.
• Có 50% số điểm còn lại không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

19 2 13 15 2

OUTPUT

8

Giải thích: ~n = 19, m_{1} = 2, m_{2} = 13, m_{3} = 15~ và ~d = 2~.

• Hàng cà chua ban đầu: GRGGGGGGGGGGRGRGGGG
• Sau ngày thứ nhất: RRRGGGGGGGGRRRRRGGG
• Sau ngày thứ hai: RRRRGGGGGGRRRRRRRGG

Vậy sau hai ngày còn ~8~ quả cà chua còn xanh.

Ví dụ 2

INPUT

50 1 50 25 7

OUTPUT

19

Một vùng đất hình chữ nhật có thể xem như một lưới ô vuông tạo bởi ~n~ dòng và ~m~ cột. Trên vùng đất đó người ta đã xây dựng ~h~ đường ngang và ~v~ đường dọc. Các đường này là những đường thẳng đi qua biên của các ô trên cùng dòng hay cùng cột, bắt đầu và kết thúc trên biên của vùng đất. Các đường ngang được đánh số từ ~1~ đến ~n + 1~ từ trên xuống dưới và các đường dọc được đánh số từ ~1~ đến ~m + 1~ từ trái sang phải.

Để lên kế hoạch cho một dự án xây dựng nhà ở, người ta khảo sát vùng đất để mỗi ngôi nhà có thể xây dựng trên một mảnh đất hình vuông có diện tích ~k \times k~. Tất cả các hình vuông dựng nhà đều có diện tích bằng nhau, không phủ lên nhau, không phủ lên các con đường. Chúng có thể giáp hoặc không giáp với các con đường. Không có ô đất nào để trống. Để tiện tính toán chúng ta bỏ qua độ rộng của các con đường.

Yêu cầu

Hãy tìm những giá trị ~k~ thỏa mãn điều kiện xây dựng nhà cho dự án.

Dữ liệu đầu vào

Gồm một hoặc ba dòng:

• Dòng đầu tiên chứa bốn số nguyên ~n, m, h, v~ ~(1 \le n, m \le 10^{18},\ 0 \le h, v \le 2 \times 10^5)~.
• Nếu ~h > 0~ thì dòng tiếp theo chứa ~h~ số nguyên ~h_i,\ i = 1, 2, ..., h~ ~(1 \le h_{i} \le n + 1;\ 1 \le i \le h)~ là chỉ số các con đường ngang, tương tự nếu ~v > 0~ thì dòng tiếp theo chứa các ~v_i,\ i = 1, 2, ..., v~ ~(1 \le v_{i} \le m + 1;\ 1 \le i \le v)~ là chỉ số của các đường dọc. Không có trường hợp ~h = 0~ và ~v > 0~ hoặc ~h > 0~ và ~v = 0~. Các ~h_i~ và ~v_i~ có thể trùng nhau.

Các số trên một dòng cách nhau dấu cách.

Dữ liệu đầu ra

Gồm hai dòng:

• Dòng đầu ghi một số là số giá trị ~k~ tìm được;
• Dòng thứ hai là các giá trị ~k~ tìm được, các số ghi cách nhau dấu cách và theo thứ tự tăng.

Ràng buộc dữ liệu

• Có 50% số điểm có ~h = 0~ và ~v = 0~.
• Có 50% số điểm có ~h > 0~ và ~v > 0~. Không có hình chữ nhật nào được tạo ra bởi việc chia của các con đường này có kích thước cạnh lớn hơn ~10^{14}~.

Ví dụ

Ví dụ 1

INPUT

2 4 0 0

OUTPUT

2
1 2

Ví dụ 2

INPUT

6 8 1 1
3
3

OUTPUT

2
1 2

Giải thích: ~n = 6, m = 8, h = 1, v = 1~ và ~h_1 = 3, v_1 = 3~.

Các đường nét đứt là các con đường ngang, dọc.

Với ~k = 1~ luôn thỏa mãn, ~k = 2~ được thực hiện như hình vẽ.

Ví dụ 3

INPUT

44 36 3 6
25 33 9
9 37 9 21 29 9

OUTPUT

3
1 2 4

An tạo cho mình một mật khẩu bằng cách sinh ra một dãy ~S~ gồm các chữ cái Latin in thường viết liền nhau. Sau đó bạn thực hiện các bước sau:

1. Sắp các chữ cái trong mật khẩu theo thứ tự từ điển;
2. Trong dãy ký tự đã sắp, An tạo ra một dãy mới ~T~ từ ~S~ bằng cách chỉ giữ lại số lượng chữ cái tương ứng với số thứ tự của nó trong bảng chữ cái:
   • Nếu có nhiều hơn một chữ cái a thì chỉ giữ lại một;
   • Nếu có nhiều hơn hai chữ cái b thì chỉ giữ lại hai, ngược lại thì giữ nguyên;
   • Nếu có nhiều hơn ba chữ cái c thì chỉ giữ lại ba, ngược lại thì giữ nguyên;
   • ...
   • Nếu có nhiều hơn ~26~ chữ cái z thì chỉ giữ lại ~26~, ngược lại thì giữ nguyên.
3. Ghép dãy ~T~ vào sau dãy ~S~ và ghi dãy thu được vào sổ tay của mình.

Sau một thời gian, An không thể tìm ra mật khẩu (~S~) của mình nữa.

Yêu cầu

Từ dãy chữ cái đã ghi trong sổ tay của An, bạn hãy giúp An tìm lại mật khẩu (~S~).

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 5 \times 10^5)~ là số chữ của dãy chữ cái trong sổ tay của An;
• Dòng thứ hai chứa dãy chữ cái hợp lệ đó.

Dữ liệu đầu ra

Gồm một dòng ghi dãy chữ cái Latin in thường là mật khẩu (~S~) tìm được.

Ràng buộc dữ liệu

• Có 20% số điểm: mật khẩu chỉ gồm chữ cái a;
• Có 40% số điểm: mật khẩu chỉ gồm các chữ cái giống nhau;
• Có 40% số điểm còn lại không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

19
abbracadabraabbcdrr

OUTPUT

abbracadabra

Giải thích: Dãy ký tự tương ứng với mật khẩu abbracadabra sau khi sắp xếp theo thứ tự từ điển ta có aaaaabbbcdrr. Do a có nhiều hơn một nên chỉ giữ lại một, b chỉ giữ lại hai, c, d, rr giữ nguyên (r có thứ tự ~18~ trong bảng chữ cái). Dãy ~T~ thu được abbcdrr. Dãy ký tự được ghi vào sổ tay là dãy abbracadabraabbcdrr.

Ví dụ 2

INPUT

10
dddddddddd

OUTPUT

dddddd

Giải thích: Do mật khẩu dddddd có nhiều hơn bốn chữ cái nên An chỉ giữ lại bốn. ~4~ chữ d ghép vào sau mật khẩu tạo ra dãy ghi trong sổ tay có 10 chữ cái d.

Cho dãy số nguyên dương gồm ~n~ số hạng ~a_1, a_2, ..., a_n~.

Yêu cầu

Có ~q~ truy vấn, mỗi truy vấn gồm hai chỉ số ~l_i, r_i~ ~(1 \le l_{i} \le r_{i} \le n;\ 1 \le i \le q)~, hãy trả lời trong đoạn con ~a_l, a_{l + 1}, ..., a_r~ có bao nhiêu số hạng khác nhau.

Dữ liệu đầu vào

Gồm ~q + 3~ dòng:

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9;\ i = 1, 2, ..., n)~.
• Dòng thứ ba chứa số nguyên ~q~ ~(1 \le q \le 10^5)~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~l_i, r_i~ ~(1 \le l_i \le r_i \le n;\ i = 1, 2, ..., q)~ tương ứng với một truy vấn.

Các số trên một dòng cách nhau dấu cách.

Dữ liệu đầu ra

Tương ứng với mỗi truy vấn theo thứ tự từ dữ liệu vào ghi ra một dòng gồm một số là kết quả tìm được của truy vấn đó.

Ràng buộc dữ liệu

• Có 30% số điểm có ~n \le 10^4;\ q \le 10^4~.
• Có 30% số điểm có ~n \le 10^4;\ q \le 10^5~.
• Có 40% số điểm có ~n \le 10^5;\ q \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

9
33 5 6 7 8 112 6 6 6
4
1 9
2 7
5 9
3 4

OUTPUT

6
5
3
2