Một nhà máy sản xuất có ~N~ công nhân, trong một tháng mỗi công nhân hoàn thành được số sản phẩm lần lượt là ~a_1, a_2, ..., a_N~. Để đánh giá năng suất làm việc của các công nhân, người ta thống kê xem có bao nhiêu công nhân sản xuất được số sản phẩm trong khoảng [~p~, ~q~].

Yêu cầu: Em hãy giúp nhà máy thống kê số công nhân có số sản phẩm thoả mãn yêu cầu trên.

Dữ liệu vào:

• Dòng đầu tiên ghi số ~N~ là số công nhân của nhà máy, ~T~ (~n ≤ 10^5~, ~T ≤ 10^5~) là số khoảng [~p~, ~q~] cần thống kê.
• Dòng tiếp theo ghi ~n~ số nguyên dương lần lượt là các giá trị ~a_1,a_2…,a_n (a_i ≤ 10^9~).
• ~T~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~p~, ~q~ (~p, q ≤10^9~).

Dữ liệu ra:

• Gồm ~T~ dòng, mỗi dòng là kết quả tương ứng với từng khoảng [~p, q~]

Ví dụ:

Input

5 3 
1 3 5 7 9 
2 6 
1 10
10 20

Output

2
5
0

Ràng buộc:

• 30% test thỏa ~2 ≤ n ≤ 100~
• 40% test thỏa ~2 ≤ n ≤ 1000~
• 30% test thỏa ~2 ≤ n ≤ 100000~

Ví dụ:

Input1:

2 4 3

Output1:

-1

Input2:

2 7 3

Output2:

5

Một công ty có ~n~ sản phẩm, sản phẩm thứ i có chất lượng là ~a_i~ (~1\le a_i \le 10^6~). Mỗi ngày công ty phải giao đúng ~k~ sản phẩm nếu số sản phẩm của công ty nhiều hơn hoặc bằng ~k~, ngược lại phải giao hết số sản phẩm theo nguyên tắc:

• Ở ngày đầu tiên chất lượng sản phẩm được giao không nhỏ hơn 1.
• Ở ngày thứ hai chất lượng sản phẩm được giao không nhỏ hơn 2.
• Ở ngày thứ ba chất lượng sản phẩm được giao không nhỏ hơn 3. ………
• Ở ngày thứ i chất lượng sản phẩm được giao không nhỏ hơn i. ………
  Quá trình giao hàng sẽ dừng lại khi đã giao hết hàng, hoặc không thể giao được nữa. Do có chiến lược giao hàng tối ưu, nên công ty đã giao hết số sản phẩm.

Yêu cầu: Hãy tìm giá trị nhỏ nhất của ~k~.

Dữ liệu vào:

• Dòng đầu: Số nguyên dương ~n~ (~n < 10^6~)
• Dòng hai: Dãy số nguyên dương ~a_1, a_2, a_3,…, a_n~ (~a_i < 10^6~, ~1 \le i \le n~)

Dữ liệu ra:

• Một số nguyên duy nhất theo yêu cầu.

Ví dụ:

Input

7
3 1 4 2 3 4 4

Output

2

Giải thích:

• Nếu mỗi ngày công ty giao 1 sản phẩm thì còn lại ít nhất 3 sản phẩm. Chẳng hạn ngày đầu giao sản phẩm có chất lượng 1, ngày thứ hai giao sản phẩm có chất lượng là 2, ngày thứ ba giao sản phẩm có chất lượng là 3, ngày thứ tư giao sản phẩm có chất lượng là 4. Như vậy còn 3 sản phẩm không được giao là 3, 4, 4.
• Nếu mỗi ngày công ty giao 2 sản phẩm và do công ty có chiến lược hợp lí nên đã giao hết hàng, chẳng hạn: ngày đầu giao sản phẩm có chất lượng 1 và 2, ngày thứ hai giao 2 sản phẩm có chất lượng là 3, ngày thứ 3 giao 2 sản phẩm có chất lượng là 4, ngày thứ tư giao sản phẩm còn lại có chất lượng 4.

Giới hạn dữ liệu:

• 60% bộ test có ~n <10^3~;
• 40% bộ test không giới hạn gì thêm.

Xe tăng là một phương tiện có cách di chuyển rất đặc biệt. Các bánh xe của nó trải dài trên nền đất để tăng diện tích tiếp xúc, từ đó giảm áo lực lên nền, Giả sử xe tăng đang muốn đi từ ~p~ đến ~q~, ta có thể chia đoạn đất này thành ~𝑛~ đoạn nhỏ, đoạn thứ ~𝑖~ có độ cứng ~𝑎_𝑖~. Một xe tăng có chiều dài ~𝑙~, khối lượng ~𝑚~ có thể đi qua nếu tại mọi thời điểm, nó luôn đứng trên vùng đất có tổng độ cứng không nhỏ hơn ~𝑚~ (có nghĩa là mọi đoạn con liên tiếp độ dài ~𝑙~ của dãy ~𝑎~ đều phải có tổng lớn hơn hoặc bằng ~𝑚~).

Yêu cầu: Cho biết khối lượng ~𝑚~ của xe tăng, hãy tính chiều dài ~𝑙~ nhỏ nhất có thể có của nó để xe tăng đi qua được vùng đất này.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên ~𝑚~,~𝑛~.

• Dòng tiếp theo chứa lần lượt các số ~𝑎_1,𝑎_2,…,𝑎_𝑛~.

Dữ liệu luôn đảm bảo tổng của mảng ~𝑎~ lớn hơn hoặc bằng ~𝑚~.

Giới hạn:

• ~1 ≤𝑛≤ 10^5~

• ~1 ≤𝑎_𝑖,𝑚 ≤ 10^9~

Kết quả:

Một số nguyên duy nhất là chiều dài ngắn nhất có thể của xe tăng.

Ví dụ:

Input

6 5

3 2 1 4 5

Output

3

Cho hai dãy số A có N phần tử, B có M phần tử, các phần tử là các số nguyên ~A_i~ . Bạn hãy tính số lượng giá trị của A có mặt trong B.

Input:

• Dòng 1: Ghi hai số nguyên N và M.
• Dòng 2: Ghi N số có trong tập A.
• Dòng 3: Ghi M số có trong tập B.

Output:

• Dòng 1: Ghi hai số nguyên K là số lượng các số của tập A có trong tập B.
• Dòng 2: ghi K số nguyên là các phần tử giao của 2 tập theo thứ tự tăng dần.

Example:

Input:

4 5
2 5 5 6 
7 5 5 6 7

Output:

2
5 6

Constraints:

~0 < M, N < 10^5~ ; ~0 \le A_i \le 10^9~

Cho hai xâu ký tự ~S~ và ~T~ chỉ gồm các chữ cái in hoa tiếng Anh (~A–Z~).

Hãy tìm xâu con liên tiếp ngắn nhất của ~S~ sao cho xâu con đó chứa tất cả các ký tự của ~T~, bao gồm cả số lần xuất hiện của từng ký tự.

Nếu có nhiều xâu con thỏa mãn, hãy in ra xâu có độ dài nhỏ nhất. Nếu không tồn tại, in ra xâu rỗng.

Dữ liệu vào

• Dòng 1: xâu ~S~ (~1≤∣𝑆∣≤10^5~)
• Dòng 2: xâu ~T~ (~1≤∣𝑇∣≤10^5~)

Dữ liệu ra

• In ra xâu con ngắn nhất của ~S~ thỏa mãn yêu cầu. Nếu không tồn tại, in ra xâu rỗng (không in gì)

Ví dụ

Input1:

ADOBECODEBANC
ABC

Output1:

BANC

Input2:

AAABBC
ABC

Output2:

ABBC