Cây chỉ số nhị phân (Binary Indexed Tree), hay còn gọi là Fenwick Tree, là một cấu trúc dữ liệu dùng để lưu tổng cộng dồn của một mảng một cách hiệu quả. Cấu trúc này cho phép cập nhật một phần tử và truy vấn tổng cộng dồn tới một vị trí trong ~O(log \space n)~.

Cho dãy số nguyên ~A~ đánh số từ 1, ta gọi dãy ~B~ là cây chỉ số nhị phân được xây dựng dựa trên ~A~ như sau:

• Với mỗi chỉ số ~i~, ta xét biểu diễn nhị phân của ~i~, đánh số các bit theo thứ tự từ nhỏ đến lớn bắt đầu từ 0.
• Gọi vị trí bit 1 nhỏ nhất của ~i~ là ~k~.
• Khi đó ~B[i]~ là tổng của ~2^k~ phần tử liên tiếp của ~A~, kết thúc tại ~i~.
• Ví dụ: ta có ~6 = 2^2 + 2^1~, suy ra ~k=1~, do đó ~B[6] = A[5] + A[6]~.

Sau đây là hình ảnh minh họa cây chỉ số nhị phân cho dãy gồm 8 phần tử, lấy từ VNOI Wiki, với "bit" chính là dãy ~B~:

Đăng xây dựng một hệ thống cơ sở dữ liệu hỗ trợ tính toán nhanh, trong đó có dùng một cây chỉ số nhị phân. Tuy nhiên, do một sự cố mất điện, ổ cứng của máy đã bị hư hỏng, và Đăng đã mất toàn bộ dãy ~A~, chỉ còn lại dãy ~B~. Ngay cả dãy ~B~ cũng bị mất một số phần tử. Với những phần tử trong dãy lưu ở những vùng ổ cứng bị hư hỏng, khi đọc lên sẽ được thay bằng kí tự "?".

Từ những phần tử của dãy ~B~ còn lại, bạn hãy khôi phục lại nhiều phần tử nhất có thể của dãy ~A~.

Input

Dòng đầu tiên của input chứa số nguyên ~N~ ~(1 ≤ N ≤ 10^5)~, số phần tử của dãy ~B~.

Dòng thứ hai chứa ~N~ số nguyên không âm là các phần tử của dãy ~B~, cách nhau bởi khoảng trắng.

Output

In ra dãy ~A~ đã được khôi phục trên một dòng, với dấu "?" cho những vị trí không thể khôi phục được, các phần tử cách nhau bởi một khoảng trắng.

Các phần tử của dãy ~A~ là các số nguyên không âm có giá trị không vượt quá ~10^4~.

Sample Input

2
? 2

Sample Output

? ?

Subtask

• ~30\%~ số điểm của bài tương ứng với các test không có dấu "?" trong input.

Note

Trong test đề bài, ta chỉ biết được tổng của 2 phần tử, thông tin này là không đủ để ta suy ra từng phần tử là gì.