Hôm nay là 1 ngày đẹp trời, Kluco vừa học xong cách đếm số, cô giáo hpgiakhang1405 đã cho Kluco 1 bài tập đếm số như sau:

Cô giáo cho Kluco ~n~ số tự nhiên và ~q~ câu hỏi ~(3 \leq n, q \leq 10^6)~. Với mỗi câu hỏi chứa 1 số tự nhiên ~q_i~, Kluco sẽ phải đếm số lượng số lượng phần tử ~q_i~ có trong ~n~ số tự nhiên đã cho.

Vì cô giáo này là ác quỷ, nên số lượng số quá nhiều khiến Kluco choáng váng, nên anh ấy đã nhờ bạn giúp anh ấy hoàn thành bài tập này.

Input

• Dòng đầu tiên số nguyên ~n~ ~(3 \leq n \leq 10^6)~
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_i~ ~(1 \leq a_i \leq 10^6)~
• Dòng tiếp theo chứa số nguyên ~q~ ~(3 \leq q \leq 10^6)~
• ~q~ dòng tiếp theo chứa các số ~q_i~ ~(1 \leq q_i \leq 10^6)~

Output

• ~q~ dòng là số lượng số ~q_i~ có trong ~n~ số tự nhiên đã cho

Sample Input 1

3
1 1 2
3
1
2
3

Sample Output 1

2
1
0

Sau mỗi buổi tập luyện, banmkh62 thường mang đến các chai nước ngọt để làm phần thưởng cho những sinh viên xuất sắc. Mỗi chai nước ngọt được gắn một số nguyên ~a_i~. Sau khi trao thưởng, banmkh62 còn có các chai nước "may mắn" dành cho các sinh viên có cặp số trên hai chai nước bất kỳ, ~a_i~ và ~a_j~ ~(i < j)~, thỏa mãn điều kiện ~a_i + a_j = k~, với ~k~ là một số nguyên cho trước.

Nhiệm vụ của bạn là tìm xem banmkh62 cần phải chuẩn bị bao nhiêu chai nước "may mắn" dựa trên điều kiện này.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~:
  • ~n~ là số lượng chai nước ngọt ~(1 \le n \le 10^3).~
  • ~k~ là giá trị tổng tuyệt đối mà hai số nguyên trên chai nước phải đạt ~(1 \le k \le 10^4)~.
• Dòng thứ hai chứa n số nguyên ~a_1, a_2,...,a_n~ ~(0 \le a_i \le 10^4)~, là các số ghi trên từng chai nước ngọt.

Output

• In ra một số nguyên duy nhất là số lượng cặp số may mắn thỏa mãn điều kiện trên.

Sample Input 1

8 7
6 2 3 1 6 6 6 4

Sample Output 1

5

Sau mỗi buổi tập luyện, banmkh62 thường mang đến các chai nước ngọt để làm phần thưởng cho những sinh viên xuất sắc. Mỗi chai nước ngọt được gắn một số nguyên ~a_i~. Sau khi trao thưởng, banmkh62 còn có các chai nước "may mắn" dành cho các sinh viên có cặp số trên hai chai nước bất kỳ, ~a_i~ và ~a_j~ ~(i < j)~, thỏa mãn điều kiện ~a_i + a_j = k~, với ~k~ là một số nguyên cho trước.

Nhiệm vụ của bạn là tìm xem banmkh62 cần phải chuẩn bị bao nhiêu chai nước "may mắn" dựa trên điều kiện này.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~:
  • ~n~ là số lượng chai nước ngọt ~(1 \le n \le 10^5).~
  • ~k~ là giá trị tổng tuyệt đối mà hai số nguyên trên chai nước phải đạt ~(1 \le k \le 10^6)~.
• Dòng thứ hai chứa n số nguyên ~a_1, a_2,...,a_n~ ~(0 \le a_i \le 10^6)~, là các số ghi trên từng chai nước ngọt.

Output

• In ra một số nguyên duy nhất là số lượng cặp số may mắn thỏa mãn điều kiện trên.

Sample Input 1

8 7
6 2 3 1 6 6 6 4

Sample Output 1

5

Ở một vương quốc nọ vô cùng rộng lớn có diện tích ~N \times M~ hẹt ta nhưng lại được cai trị bởi một vị vua bất tài tên là Kluco, vì sự kém cỏi của mình nên vương quốc thường xuyên bị các thế lực đen tối xâm chiếm và c.ư.ớ.p bóc, để an toàn Kluco đã phân bổ đều các thành phố trên toàn bộ lãnh thổ để giảm thiểu thiệt hại khi bị các thế lực khác xâm lược nên cứ mỗi 1 hẹt ta vuông thì sẽ mọc lên 1 thành phố ở trung tâm.

Vào một ngày nọ ma vương unKluco là một phiên bản Kluco hắc ám tới từ một vũ trụ song song và thấy vô cùng ngứa mắt với cách phân bổ này của Kluco nên unKluco đã tấn công vào vương quốc của Kluco để bóc lột, nếu không đưa đủ vàng thì unKluco sẽ xoá sổ toàn bộ vương quốc.

Ma vương unKluco rất ghét hình vuông nên đã đề nghị cứ mỗi bốn thành phố riêng biệt tạo nên một hình vuông hoàn chỉnh thì unKluco sẽ thu của Kluco ~1~ thỏi vàng. Vì bất tài nên Kluco cũng chả giỏi tính toán, trong lúc không thể tính được số vàng phải trả là bao nhiêu thì Kluco nhớ ra rằng vương quốc mình dẫn còn một lập trình viên tài ba đó chính là bạn.

Bạn hãy giúp Kluco pha này nhé, biết rằng ~1 \leq N,M \leq 1000~

Input

• Hai số nguyên ~N,M (1 \leq N,M \leq 1000)~ , đại diện cho chiều dài và chiều rộng của vương quốc.

Output

• Một số nguyên duy nhất là số thỏi vàng unKluco nhận được.

Sample Input

3 3

Sample Output

6

Ở một vương quốc nọ vô cùng rộng lớn có diện tích ~N \times M~ hẹt ta nhưng lại được cai trị bởi một vị vua bất tài tên là Kluco, vì sự kém cỏi của mình nên vương quốc thường xuyên bị các thế lực đen tối xâm chiếm và c.ư.ớ.p bóc, để an toàn Kluco đã phân bổ đều các thành phố trên toàn bộ lãnh thổ để giảm thiểu thiệt hại khi bị các thế lực khác xâm lược nên cứ mỗi 1 hẹt ta vuông thì sẽ mọc lên 1 thành phố ở trung tâm.

Vào một ngày nọ ma vương unKluco là một phiên bản Kluco hắc ám tới từ một vũ trụ song song và thấy vô cùng ngứa mắt với cách phân bổ này của Kluco nên unKluco đã tấn công vào vương quốc của Kluco để bóc lột, nếu không đưa đủ vàng thì unKluco sẽ xoá sổ toàn bộ vương quốc.

Ma vương unKluco rất ghét hình vuông nên đã đề nghị cứ mỗi bốn thành phố riêng biệt tạo nên một hình vuông hoàn chỉnh thì unKluco sẽ thu của Kluco ~1~ thỏi vàng. Vì bất tài nên Kluco cũng chả giỏi tính toán, trong lúc không thể tính được số vàng phải trả là bao nhiêu thì Kluco nhớ ra rằng vương quốc mình dẫn còn một lập trình viên tài ba đó chính là bạn.

Bạn hãy giúp Kluco pha này nhé, biết rằng ~1 \leq N,M \leq 10^9~

Input

• Gồm Q dòng ~Q (1 \leq Q \leq 1000)~ , đại diện cho ~Q~ truy vấn của ~Q~ vũ trụ khác nhau, lưu ý input không có ~Q~.
• Mỗi dòng có hai số nguyên ~N,M (1 \leq N,M \leq 10^9)~ , đại diện cho chiều dài và chiều rộng của vương quốc.

Output

• Một số nguyên duy nhất là số thỏi vàng unKluco nhận được.

Sample Input

3 3

Sample Output

6

Giới Hạn

• Có 50% số test với ~N, M \leq 10^6~
• Còn lại không có ràng buộc nào

Thầy Luna cho đề kiểm tra cho ~n~ SV làm và sau khi chấm thì phát hiện ra nhiều bài bằng điểm nhau. Thực ra đó là chuyện bình thường nhưng thầy lại khá nhạy cảm nên muốn gọi tất cả các cặp SV bằng điểm nhau lên vấn đáp lại xem có copy bài của nhau hay không. Hỏi thầy phải hỏi tất cả bao nhiêu cặp?

Input

Dòng đầu tiên gồm số SV là ~n~, trong đó ~2 \le n \le 10^5.~ Dòng tiếp theo gồm điểm số của các SV, các số này là số tự nhiên có giá trị không quá ~10^6.~

Output

Số cặp SV thầy cần vấn đáp.

Sample input 1

5
1 1 1 2 2

Sample output

4

Giải thích: nếu đánh số các SV là ~1,2,3,4,5~ thì các cặp bị vấn đáp sẽ là: ~(1,2),(2,3),(3,1)~ và ~(4,5).~

Một từ hoặc câu được gọi là pangram nếu nó chứa tất cả các chữ cái của bảng chữ cái trong ngôn ngữ đó ít nhất một lần. Pangram thường được sử dụng để thử nghiệm kiểu chữ trong in ấn và thiết bị đầu ra.

Bạn có một chuỗi gồm các chữ cái Latin viết hoa và viết thường. Hãy kiểm tra xem chuỗi này có phải là pangram hay không. Một chữ cái được coi là có mặt trong chuỗi nếu nó xuất hiện dưới dạng viết hoa hoặc viết thường.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 100)~ - độ dài của chuỗi cần kiểm tra.
• Dòng thứ hai bao gồm một chuỗi chứa các chữ cái Latin viết hoa và viết thường.

* Output *

• In YES nếu chuỗi là pangram, ngược lại in NO.

Sample Input 1

26
MGJYIZDKsbhpVeNFlquRTcWoAx

Sample Output 1

YES

Cho một chuỗi có độ dài là ~n~ có thể đã bị mã hóa theo thuật toán sau:

• Lặp qua các ước của ~n~ theo thứ tự giảm dần (tức là từ ~n~ đến ~1~).
• Với mỗi ước số ~d~, đảo ngược đoạn con ~s[1..d]~ (tức là đoạn con bắt đầu từ vị trí 1 và kết thúc tại ~d~).

Ví dụ, thuật toán trên được áp dụng cho chuỗi ~s = iuhcoder~ dẫn đến các thay đổi sau:

• iuhcoder → redochui → oderchui → doerchui.

Bạn được cho một chuỗi ~t~ đã được mã hóa (độ dài của chuỗi không vượt quá ~100~). Nhiệm vụ của bạn là giải mã chuỗi này, tức là tìm một chuỗi ~s~ sao cho thuật toán trên cho ra chuỗi ~t~. Có thể chứng minh chuỗi ~s~ này luôn tồn tại và là duy nhất.

Input

• Dòng đầu tiên của đầu vào chứa chuỗi ~t~ chỉ bao gồm các chữ cái Latin viết thường.

* Output *

• In ra chuỗi một ~s~ là yêu cầu của đề bài.

Sample Input 1

doerchui

Sample Output 1

iuhcoder

Sample Input2

uvila

Sample Output2

alivu

Hôm nay là 1 ngày đẹp trời, Kluco vừa học xong cách đếm số, cô giáo hpgiakhang1405 đã cho Kluco 1 bài tập đếm số như sau:

Cô giáo cho Kluco ~n~ số tự nhiên và ~q~ câu hỏi. Với mỗi câu hỏi chứa 1 số tự nhiên ~q_i~, Kluco sẽ phải đếm số lượng số lượng phần tử ~q_i~ có trong ~n~ số tự nhiên đã cho.

Vì cô giáo này là ác quỷ, nên số lượng số quá nhiều khiến Kluco choáng váng, nên anh ấy đã nhờ bạn giúp anh ấy hoàn thành bài tập này.

Input

• Dòng đầu tiên số nguyên ~n~ ~(1 \leq n \leq 2 \times 10^5)~.
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_i~ ~(-10^9 \leq a_i \leq 10^9)~.
• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \leq q \leq 2 \times 10^5)~.
• ~q~ dòng tiếp theo chứa các số ~q_i~ ~(-10^9 \leq q_i \leq 10^9)~.

Output

• ~q~ dòng là số lượng số ~q_i~ có trong ~n~ số tự nhiên đã cho.

Sample Input

3
1 1 2
3
1
2
3

Sample Output

2
1
0

Hoan thực sự rất thích toán. Một ngày nọ, khi đang giải một bài toán khác, anh ấy nghĩ ra một cái cây khá thú vị. Cây này được xây dựng như sau:

Ban đầu chỉ có một đỉnh mang số 1 là gốc cây. Sau đó Hoan thêm 2 đỉnh con vào sau gốc và gán 2 số liên tiếp là 2 và 3 tương ứng. Sau đó Hoan lại thêm các phần tử con vào các đỉnh theo thứ tự số lượng tăng dần bắt đầu từ 2, gán cho đỉnh con các số chưa được sử dụng lớn hơn 0. Kết quả là Hoan đã có một cây nhị phân vô hạn với đỉnh gốc là 1, với mỗi đỉnh có 2 đỉnh con và số đỉnh được sắp xếp tuần tự theo từng lớp. như hình bên dưới:

Hoan tự hỏi tổng các giá trị các đỉnh trên đường đi từ đỉnh 1 tới đỉnh x là bao nhiêu?. Vì Hoan khá lười nên anh ấy đã nhờ bạn giúp anh ấy tìm tổng đó.

INPUT

Dòng đầu tiên chứa số nguyên n là đỉnh mà Hoan muốn tính (~1 \leq n \leq 10^{18}~)

OUTPUT

Một số nguyên duy nhất là tổng mong muốn

SAMPLE INPUT 1

1

SAMPLE OUTPUT 1

1

SAMPLE INPUT 2

6

SAMPLE OUTPUT 2

10

giải thích test đề: ở test 1 có thể thấy từ đỉnh 1 tới đỉnh 1 thì chỉ có duy nhất 1 đỉnh mang giá trị 1 nên kết quả là 1

ở test 2 có thể thấy từ đỉnh 1 tới đỉnh 6 có 3 đỉnh là 1,3,6 và tổng cần tìm là 1 + 3 + 6 = 10.

Cho mảng a gồm có n phần tử ~a_0~, ~a_1~, ... ~a_{n-1}~ và một số nguyên k. Hãy in ra phần tử lớn thứ k của mảng a sau khi đã sắp sếp tăng dần.

Lưu ý là chỉ số bắt đầu từ 0.

Input

Gồm 2 dòng:

Dòng thứ nhất là số phần tử của mảng n và số k (~1 ≤ n ≤ 10^3~, 0 ≤ k ≤ n-1)

Dòng thứ hai gồm n số nguyên ~a_0~, ~a_1~, ... ~a_{n-1}~.

Output

Một dòng duy nhất là số lớn thứ k của mảng a.

Examples

Input

8 3  
4 2 6 3 6 4 5 7 

Output

4 

Mảng sau khi đã sắp sếp tăng dần là: 2, 3, 4, 4, 5, 6, 6, 7. Vì vậy phần tử lớn thứ 3 là 4 (chỉ số bắt đầu từ 0)

Ba người chơi một trò chơi như sau: mỗi người viết ra ~n~ từ khác nhau, mỗi từ có độ dài ~3~ ký tự. Sau đó, họ tính tổng điểm theo quy tắc sau:

• Nếu một từ chỉ được viết bởi một người ~-~ người đó nhận được 3 điểm.
• Nếu một từ được viết bởi hai người ~-~ mỗi người trong hai người đó nhận 1 điểm.
• Nếu một từ được viết bởi cả ba người ~-~ không ai nhận được điểm nào.

Kết thúc trò chơi, hỏi tổng điểm của ba người là bao nhiêu (số điểm ban đầu của cả ba đều bằng ~0~)?

Input

• Dòng đầu tiên số nguyên ~n~ ~(1 \leq n \leq 10^4)~ ~-~ số lượng từ được viết ra bởi mỗi người.
• Ba dòng tiếp theo, mỗi dòng chứa ~n~ từ khác nhau ~-~ các từ được viết bởi mỗi người. Mỗi từ bao gồm ~3~ ký tự tiếng Anh viết thường.

Output

Một dòng gồm ba số nguyên là số điểm của ba người chơi (theo thứ tự người chơi tăng dần).

Sample Input 1

1
abc
def
abc

Sample Output 1

1 3 1

Sample Input 2

3
orz for qaq
qaq orz for
cod for ces

Sample Output 2

2 2 6

Sample Input 3

5
iat roc hem ica lly
bac ter iol ogi sts
bac roc lly iol iat

Sample Output 3

9 11 5

Đi rừng là một hoạt động được tổ chức thường xuyên trong câu lạc bộ để giúp các thành viên thư giãn sau những giờ phút miệt mài với bàn phím và dòng code. Nhưng hôm nay, không chỉ là một buổi đi rừng thông thường, mà là một cuộc thi kỹ năng sinh tồn được tổ chức ngay giữa khu rừng!

Có ~n~ thành viên tham gia cuộc thi. Thành viên thứ ~i~ được đánh giá kỹ năng thông qua chỉ số ~a_i~. Ban tổ chức quyết định chia các thành viên thành các nhóm liên tiếp, mỗi nhóm phải cạnh tranh dựa trên kỹ năng yếu nhất của nhóm mình. Cụ thể, kỹ năng của một nhóm được tính bằng giá trị nhỏ nhất trong chỉ số kỹ năng của các thành viên trong nhóm.

Để tăng độ kịch tính, mỗi đội trưởng phải báo cáo cho ban tổ chức rằng, với mỗi kích thước nhóm ~x~ (số thành viên trong nhóm là ~x~), nhóm mạnh nhất có thể đạt được kỹ năng cao nhất là bao nhiêu.

AliVu, người đứng đầu ban tổ chức, rất tò mò về kết quả này và muốn biết kỹ năng tối đa của nhóm mạnh nhất cho mỗi kích thước nhóm ~x~ ~(1 \le x \le n)~.

Input

• Dòng đầu tiên gồm một số nguyên ~n~ ~(1 \le n \le 2\times10^5)~ - số lượng thành viên tham gia.
• Dòng thứ hai là ~n~ số nguyên ~a_1, a_2,..., a_n~ ~(1 \le a_i \le 10^9~ - chỉ số kỹ năng của từng thành viên.

Output

• In ra ~n~ số nguyên trên một dòng. Với mỗi ~x~ ~(1 \le x \le n)~, in ra kỹ năng tối đa của nhóm mạnh nhất có kích thước là ~x~.

Sample Input 1

10  
1 2 3 4 5 4 3 2 1 6

Sample Output 1

6 4 4 3 3 2 2 1 1 1

Bạn được cho một mảng gồm ~n~ phần tử, nhiệm vụ của bạn là với mỗi vị trí hãy tìm phần tử gần nhất về phía trái có giá trị nhỏ hơn phần tử hiện tại.

Input

• Dòng đầu tiên gồm một số nguyên ~n~ ~(1 \le n \le 2\times10^5)~ - kích thước của mảng.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,...,a_n~ ~(1 \le a_i \le 10^9)~- các giá trị của mảng.

Output

• In ra ~n~ số nguyên theo yêu cầu của bài toán, nếu tại vị trí không có phần tử nào nhỏ hơn hãy in ra ~0~.

Sample Input

8
2 5 1 4 8 3 2 5

Sample Output

0 1 0 3 4 3 3 7

Takahashi, người làm việc cho một nhà hàng pizza, đang làm một chiếc pizza phô mai thơm ngon cho bữa ăn nhân viên. Trước mặt anh có ~N~ loại phô mai khác nhau.

• Độ ngon của loại phô mai thứ ~i~ là ~A_i~ (tính theo mỗi gram).
• Có ~B_i~ gram phô mai của loại này.

Tổng độ ngon của pizza sẽ là tổng độ ngon của các loại phô mai được sử dụng trên chiếc pizza.

Để tránh lãng phí, chiếc pizza có thể chứa tối đa ~W~ gram phô mai. Hãy tìm độ ngon tối đa mà chiếc pizza có thể đạt được khi sử dụng các loại phô mai, với giới hạn là ~W~ gram.

Input

Dòng đầu tiên chứa hai số nguyên ~N~ và ~W~ (~1 \leq N \leq 3 \cdot 10^5, 1 \leq W \leq 3 \cdot 10^8~).

~N~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~A_i~ và ~B_i~ tương ứng (~1 \leq A_i \leq 10^9, 1 \leq B_i \leq 10^3~).

Output

Ghi một số nguyên dương duy nhất là đáp án của bài toán.

Sample Input 1

3 5
3 1
4 2
2 3

Sample Output 1

15

Sample Input 2

4 100
6 2
1 5
3 9
8 7

Sample Output 2

100

Cho một tập hợp ~A~ rỗng và ~Q~ truy vấn, hãy xử lý từng truy vấn theo thứ tự. Mỗi truy vấn thuộc một trong ba dạng sau:

• ~1~ ~x~: Thêm giá trị vào tập hợp ~A~.

• ~2~ ~x~ ~k~: Trong các phần tử của ~A~ nhỏ hơn hoặc bằng ~x~, hãy in ra giá trị lớn thứ ~k~. (Giá trị của ~k~ không lớn hơn 5). Nếu có ít hơn ~k~ phần tử trong ~A~ nhỏ hơn hoặc bằng ~x~, in ra ~-1~.

• ~3~ ~x~ ~k~: Trong các phần tử của ~A~ lớn hơn hoặc bằng ~x~, hãy in ra giá trị nhỏ thứ ~k~. (Giá trị của ~k~ không lớn hơn 5). Nếu có ít hơn ~k~ phần tử trong ~A~ lớn hơn hoặc bằng ~x~, in ra ~-1~.

Input

Dòng đầu tiên chứa số nguyên ~Q~ ~(1 \leq Q \leq 2 \cdot 10^5)~.

~Q~ dòng tiếp theo, mỗi dòng chứa dạng truy vấn tương ứng ~(1 \leq x \leq 10^{18}, 1 \leq k \leq 5)~.

Ouput

Với truy vấn loại ~2, 3~ hãy in ra đáp án tương ứng.

Sample Input

11
1 20
1 10
1 30
1 20
3 15 1
3 15 2
3 15 3
3 15 4
2 100 5
1 1
2 100 5

Sample Output

20
20
30
-1
-1
1

Cho số nguyên ~X~ và mảng ~A~ gồm ~N~ phần tử.

Hãy tìm số nguyên ~Y~ mà:

• ~Y~ không phải là phần tử của mảng ~A~.
• Giá trị ~|X - Y|~ là tối thiểu nhất có thể.
• Nếu có nhiều đáp án thỏa mãn, in ra giá trị ~Y~ nhỏ nhất có thể.

Input

Dòng đầu tiên chứa hai số nguyên ~X~ và ~N~ ~(1 \leq X, N \leq 100)~.

Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2,... A_N~ ~(1 \leq A_i \leq 100)~.

Output

In ra đáp án của bài toán.

Sample Input

6 5
4 7 10 6 5

Sample Output

8

Trong giờ học lập trình, thầy giáo Nghialaptrinh giao cho lớp một bài tập về dấu ngoặc. ctanh2610dona thì rất nghiêm túc, còn Godsent thì nghịch ngợm, suốt ngày ghép dấu ngoặc lung tung. Một hôm, ctanh2610dona viết lên bảng một chuỗi toàn dấu ngoặc ( và ), rồi hỏi Godsent: "Ê Bảo, chuỗi này có hợp lệ không?". Anh ấy nghe xong nhưng không hiểu, liền quay sang cầu cứu bạn. Bạn hãy giúp anh ấy nhé!

Biết rằng chuỗi ngoặc hợp lệ nghĩa là:

1. Mỗi dấu ngoặc mở ( đều phải có một dấu ngoặc đóng ) đi kèm.
2. Không được có ngoặc đóng ) xuất hiện trước ngoặc mở (.

Input

• Một chuỗi chỉ gồm các ký tự ( và ), độ dài ≤ 10^5.

Output

• In ra "YES" nếu chuỗi hợp lệ.
• In ra "NO" nếu chuỗi không hợp lệ.

Ví dụ

Input 1

(()())

Output 1

YES

Input 1

())(

Output 1

NO

Trong lớp Training K20 của CLB H3.2PL hiện tại có ~n~ học viên với mỗi học viên có chỉ số sức mạnh là ~a_i~.

Một hôm, mentor điển trai AliVu đưa ra một trò chơi như sau: AliVu có tổng cộng ~q~ cơ hội tăng chỉ số sức mạnh cho các học viên, với mỗi cơ hội ~q_i~ có một số ~x_i~ là chỉ số sức mạnh được tăng thêm cho bạn học viên nào được chọn. Tuy nhiên vì mong muốn cả lớp có sự công bằng nên với mỗi cơ hội, AliVu sẽ chọn ra bạn nào có chỉ số sức mạnh thấp nhất lớp hiện tại và tăng sức mạnh thêm cho bạn ấy một lượng là ~x_i~.

Vì số lượng là quá lớn, AliVu không thể biết đến cuối cùng, sau khi trao hết cơ hội cho các bạn thì bạn nào có chỉ số sức mạnh thấp nhất lớp hiện tại. Bạn hãy tính toán giúp AliVu nhé!

Input

• Dòng đầu tiên số nguyên ~n~ ~(1 \leq n \leq 2 \times 10^5)~ ~-~ số lượng học viên trong lớp.
• Dòng tiếp theo chứa ~n~ số nguyên không âm ~a_i~ ~(0 \leq a_i \leq 10^9)~ ~-~ chỉ số sức mạnh của các học viên.
• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \leq q \leq 2 \times 10^5)~ ~-~ số lượng cơ hội tăng sức mạnh.
• ~q~ dòng tiếp theo chứa các số ~x_i~ ~(1 \leq x_i \leq 10^9)~ ~-~ chỉ số sức mạnh được tăng thêm trong mỗi cơ hội.

Output

Một dòng duy nhất là chỉ số sức mạnh thấp nhất lớp sau khi đã thực hiện hết toàn bộ cơ hội tăng sức mạnh.

Sample Input

3
1 1 2
3
2
1
2

Sample Output

2

Có một khu rừng có độ dài ~n~ ô đất và cứ mỗi một ô đất thứ ~i~ lại mọc lên 1 cái cây có chiều cao ~a_i~. Có những con sóc bay chỉ thích sống trên đỉnh các ngọn cây và chúng rất thích bay lượn.

Những chú sóc chỉ thích bay lượn và đáp trên các ngọn cây mà:

• Cây đó phải thấp hơn hoặc bằng cây của chú sóc đang đứng.
• Sóc không thể bay xuyên qua các ngọn cây cao hơn cây đang đứng.

Có ~q~ câu hỏi rằng liệu chú sóc ở ngọn cây ~x_i~ thì có thể bay tới tối đa bao nhiêu cây.

Input

• Dòng đầu tiên có số nguyên ~N~ ~(1 \leq N \leq 5 \times 10^5)~ đại diện cho chiều dài khu rừng.
• Dòng tiếp theo có ~N~ số nguyên ~a_i~ ~(1 \leq a_i \leq N)~ đại diện cho chiều cao của cây thứ ~i~
• Dòng tiếp theo có một số nguyên ~Q~ ~(1 \leq Q \leq 5 \times 10^5)~ đại diện cho số truy vấn.
• ~Q~ dòng tiếp theo với mỗi dòng có một số nguyên ~x_i~ ~(1 \leq x_i \leq N)~ đại diện cho truy vấn của chú sóc ở vị trí thứ ~x_i~.

Output

• ~Q~ dòng tương ứng với đáp án của mỗi truy vấn là số lượng cây mà chú sóc có thể bay tới

Sample Input 1

6
8 2 3 1 3 4
2
3
4

Sample Output 1

4
1

Sample Input 2

5
3 2 3 1 5
2
1
2

Sample Output 2

4
1

Số nguyên dương ~X~ gọi là số đẹp khi: trong biểu diễn cơ số mười của ~X~ (không có số ~0~ đứng đầu), đối với mỗi cặp hai chữ số liền kề, hiệu tuyệt đối của các chữ số đó nhiều nhất là ~1~.

Ví dụ, ~122, 123, 44556677~ là các số đẹp.

Cho số nguyên ~K~ hãy tìm số nguyên đẹp nhỏ nhất thứ ~K~.

Input

Dòng duy nhất chứa số nguyên ~K~ ~(1 \leq K \leq 10^5)~.

Output

Đáp án của bài toán.

Sample Input

15

Sample Output

23

Giải thích

Các số nguyên đẹp lần lượt là: ~1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23~.

Cho một mảng gồm ~N~ số nguyên dương ~a_1,a_2,\dots,a_N~ và một số nguyên dương ~M~. Một đoạn liên tiếp ~[l,r]~ được gọi là hợp lệ nếu:

~a_l \times a_{l+1} \times \dots \times a_r~

chia hết cho ~M~.

Có ~Q~ truy vấn. Mỗi truy vấn cho hai số ~L,R~.

Với mỗi truy vấn, hãy tìm độ dài nhỏ nhất của một đoạn liên tiếp ~[l,r]~ thỏa mãn:

• ~L \leq l \leq r \leq R~;
• tích các phần tử từ ~a_l~ đến ~a_r~ chia hết cho ~M~.

Nếu không tồn tại đoạn như vậy, in ra ~-1~.

Input

• Dòng đầu gồm ba số nguyên ~N,M,Q~ ~(1 \leq N,Q \leq 2\times10^5,\ 1 \leq M \leq 10^{14})~.
• Dòng thứ hai gồm ~N~ số nguyên ~a_i~ ~(1 \leq a_i \leq 10^9)~.
• ~Q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~L,R~ ~(1 \leq L \leq R \leq N)~.

Output

Với mỗi truy vấn, in ra:

• độ dài nhỏ nhất của một đoạn hợp lệ nằm hoàn toàn trong ~[L,R]~;
• hoặc ~-1~ nếu không tồn tại.

Sample Input

5 6 6
2 3 5 2 3
1 5
1 2
2 4
3 5
3 4
4 5

Sample Output

2
2
3
2
-1
2

Giới Hạn