Cho hai số nguyên dương ~x~ và ~y~ lần lượt là số chỉ một tháng và một năm. Hãy cho biết số ngày của tháng trong năm đó.

Input

Gồm hai dòng, dòng thứ nhất gồm số nguyên dương ~x~ và dòng thứ hai gồm số nguyên dương ~y~. (~x \leq 12~, ~y \leq 3000~)

Output

In ra số ngày của tháng ~x~ trong năm ~y~.

Sample Test 1

Input:

1
2020

Output:

31

Sample Test 2

Input:

2
2020

Output:

29

Cho số nguyên dương ~n~, hãy tìm số Fibonacci thứ ~n~.

Số Fibonacci thứ ~i~ được định nghĩa như sau: ~ \begin{equation} f_i = \begin{cases} 1 & \text{nếu $i \leq 2$}\\ f_{i - 1} + f_{i - 2} & \text{nếu $i > 2$} \end{cases} \end{equation} ~

Ví dụ dãy Fibonacci cho ~10~ số đầu tiên: ~1, 1, 2, 3, 5, 8, 13, 21, 34, 55~.

Input

Gồm một số nguyên dương ~n~ duy nhất. (~n \leq 75~)

Output

In ra số Fibonacci thứ ~n~.

Subtasks

Subtask ~1~ (~40\%~): ~n \leq 40~.

Subtask ~2~ (~60\%~): Không có điều kiện gì thêm.

Sample Test 1

Input:

4

Output:

3

Sample Test 2

Input:

10

Output:

55

Cho dãy ~A~ gồm ~N~ số ~a_1, a_2, a_3, \ldots, a_N~. Bạn cần trả lời ~Q~ truy vấn, mỗi truy vấn cho một số ~k~ và bạn cần đưa ra số nhỏ nhất trong ~k~ số đầu tiên của dãy ~A~.

Input

• Dòng đầu tiên chứa hai số ~N~, ~Q~ (~N, Q \leq 10^5~).
• Dòng thứ hai chứa ~N~ số ~a_1, a_2, a_3, \ldots, a_N~ (~|a_i| \leq 10^9~).
• Dòng thứ ba chứa ~Q~ số ~k_1, k_2, k_3, \ldots, k_Q~ với các truy vấn. (~1 \leq k_i \leq N~).

Output

• In ra trên ~Q~ dòng lần lượt là kết quả của ~Q~ truy vấn.

Sample Test

Yêu cầu: Tìm giá trị lớn nhất của biểu thức ~a_i + a_j - a_k~ ~(1 \leq i < j < k \leq n)~

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên ~n~ ~(0 < n \leq 10^6)~
• Dòng thứ hai là các số nguyên ~a_1, a_2, ..., a_n~

Kết quả:

• Một dòng duy nhất ghi giá trị lớn nhất của biểu thức.

Ví dụ

Input

7
8 2 4 -2 9 1 -3

Output

20