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

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

Problem Statement

A function ~f(x)~ defined for non-negative integers ~x~ satisfies the following conditions.

• ~f(0) = 1~ .
• ~f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor)~ for any positive integer ~k~ .

Here, ~\lfloor A \rfloor~ denotes the value of ~A~ rounded down to an integer.

Find ~f(N)~ .

Constraints

• ~N~ is an integer satisfying ~0 \le N \le 10^{18}~ .

Input

The input is given from Standard Input in the following format:

~N~

Output

Print the answer.

Sample Input 1

2

Sample Output 1

3

We have ~f(2) = f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor) = f(1) + f(0) =(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3~ .

Sample Input 2

0

Sample Output 2

1

Sample Input 3

100

Sample Output 3

55

Giới thiệu: Đây là đề Training Python 3

Nam hay sử dụng mạng xã hội để giết thời gian. Trong trang danh sách trò chuyện, khi Nam gửi tin nhắn đến một người bạn nào đó, thì cuộc trò chuyện của người bạn đó sẽ xuất hiện ở đầu trang. Thứ tự đối với các cuộc trò chuyện khác không thay đổi. Trong trường hợp nếu không có cuộc trò chuyện nào với người bạn này trước đó, thì cuộc trò chuyện mới sẽ được chèn vào đầu danh sách trò chuyện.

Giả sử rằng Nam chưa có cuộc trò chuyện nào trước đó, và Nam tạo một danh sách các cuộc trò chuyện sau khi tất cả các tin nhắn của anh ấy đã được gửi đi thành công. Giả sử không có người bạn nào nhắn bất kì tin nhắn nào cho Nam.

Input

Dòng đầu tiên chứa 1 số ~n~ ~(1 \le n \le 200 000)~ - số tin nhắn mà Nam gửi.

~n~ dòng tiếp theo hiển thị người nhận tin nhắn được sắp xếp theo thứ tự tin nhắn được gửi. Tên của mỗi người tham gia cuộc trò chuyện là một dãy kí tự gồm các chữ cái tiếng Anh viết thường có độ dài tối đa là ~10~ kí tự.

Output

In tất cả những người mà Nam đã nói chuyện theo thứ tự các cuộc trò chuyện từ trên xuống dưới.

Examples 1

Input

4
alex
ivan
roman
ivan

Output

ivan
roman
alex

Examples 2

Input

8
alina
maria
ekaterina
darya
darya
ekaterina
maria
alina

Output

alina
maria
ekaterina
darya

Note

Trong test case 1, Nam gửi tin nhắn cho bạn có tên "alex", danh sách chat của Nam sẽ hiển thị như sau:

1. alex

Sau đó Nam gửi tin nhắn cho bạn "ivan", danh sách chat của Nam sẽ hiển thị như sau:

1. ivan
2. alex

Nam gửi tin nhắn thứ 3 cho người bạn tên "roman", danh sách trò chuyện của Nam sẽ được hiển thị như sau:

1. roman
2. ivan
3. alex

Nam viết tin nhắn thứ tư cho bạn bè bằng tên "ivan", cho người mà anh ta đã gửi tin nhắn, vì vậy danh sách các cuộc trò chuyện thay đổi như sau:

1. ivan
2. roman
3. alex

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

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

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