Cho dãy số ~A~ gồm ~N~ số ~a_1, a_2, a_3, ..., a_n~. Từ dãy số này Tèo tạo ra dãy số ~B~ như sau: ~b_1 = a_1, b_2 = \frac{a_1 + a_2}{2}, b_3 = \frac{a_1 + a_2 + a_3}{3}, ..., b_N = \frac{a_1 + a_2 + a_3 + ... + a_N}{N}~. Sau khi Tèo tạo xong dãy ~B~ thì xóa bỏ dãy ~A~. Tèo liền đố Tí cách tìm lại dãy ~A~ ban đầu.

Yêu cầu

Hãy lập trình giúp Tí tìm lại dãy ~A~ ban đầu.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 100)~ là số lượng số của dãy số ~B~.
• Dòng thứ hai chứa ~N~ số nguyên ~b_i~ ~(1 \le b_i \le 10^9)~.

Dữ liệu đầu ra

Gồm một dòng chứa dãy số ~A~ tìm được.

Chú ý: Cả hai dãy số chỉ gồm các số nguyên dương.

Ràng buộc dữ liệu

• Có 30% số test ứng với ~1 \le N \le 10~.
• Có 70% số test không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

5
1 2 2 3 3

OUTPUT

1 3 2 6 3

Trên thế giới có nhiều dân tộc, mỗi dân tộc có nền văn hóa của riêng họ. Dân tộc ~X~ có quan niệm về số đẹp và họ rất coi trọng số đẹp. Số đẹp của họ là số chỉ chứa chữ số ~5~ và chữ số ~8~. Được qui ước như sau: Số đẹp thứ nhất là ~5~, số đẹp thứ hai là ~8~, số đẹp thứ ba là ~55~, số đẹp thứ tư là ~58~, số đẹp thứ năm là ~85~, số đẹp thứ sáu là ~88~, ..., số đẹp thứ mười là ~588~,....

Yêu cầu

Hãy tìm số đẹp thứ ~K~.

Dữ liệu đầu vào

Gồm duy nhất số ~K~ ~(1 \le K \le 10^{18})~.

Dữ liệu đầu ra

Số đẹp thứ ~K~ tìm được.

Ràng buộc dữ liệu

• Có 60% số test ~1 \le K \le 10^8~.
• Có 40% số test không ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

10

OUTPUT

588

Trong thành phố Z có ~n~ trạm xe buýt, có ~m~ tuyến dường cho xe buýt chạy bắt đầu từ trạm ~a_i~ và kết thúc ở trạm ~b_i~, tốn khoảng thời gian ~t_i~.

Bình là một sinh viên mới vào thành phố, mỗi ngày Bình cần phải đi học bằng xe buýt từ trạm ~c_j~ đến trạm ~d_j~. Bình muốn sử dụng nhiều nhất là ~k~ tuyến cho hành trình của mình. Bình có ~q~ truy vấn: Đi từ trạm ~c_j~ đến trạm ~d_j~ chỉ sử dụng nhiều nhất là ~k~ tuyến thì thời gian ngắn nhất là bao nhiêu?

Yêu cầu

Hãy tìm thời gian ngắn nhất để đi từ trạm ~c_j~ đến trạm ~d_j~.

Dữ liệu đầu vào

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

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(2 \le n \le 70,\ 1 \le m \le 10^6)~ số trạm xe buýt và số tuyến đường.
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa ba số nguyên ~a_i, b_i~ và ~t_i~ tương ứng là đi từ trạm ~a_i~ đến trạm ~b_i~ tốn thời gian ~t_i~ ~(1 \le a_i, b_i \le n,\ 1 \le t_i \le 10^6)~.
• Dòng kế tiếp chứa hai số nguyên ~k~ và ~q~ ~(1 \le k \le 10^9,\ 1 \le q \le n^2)~, tương ứng với số tuyến đường nhiều nhất được sử dụng và số truy vấn.
• ~q~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~c_j~ và ~d_j~ ~(1 \le c_j, d_j \le n)~, tương ứng với truy vấn là đi từ trạm ~c_j~ và ~d_j~.

Dữ liệu đầu ra

Gồm ~q~ dòng tương ứng, dòng thứ ~j~ in ra dường đi ngắn nhất của truy vấn thứ ~j~ hoặc ~-1~ nếu không tìm thấy được đường đi.

Ràng buộc dữ liệu

• Có 20% số test ~k = 1~.
• Có 30% số test ~1 \le k \le n \le 7~.
• Có 50% số test không ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
1 3
1 4
4 2
3 3

OUTPUT

10
-1
0

Giải thích: Đi từ ~1~ đến ~4~ tốn chi phí ~10~, từ ~4~ tới ~2~ không có đường đi, từ ~3~ đến ~3~ chi phí là ~0~.

Ví dụ 2

INPUT

4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
2 3
1 4
4 2
3 3

OUTPUT

6
4
0