Cho một mảng \(a\) gồm \(n\) số nguyên dương phân biệt, được đánh số từ 1 đến \(n\). Định nghĩa \(p_k\) như sau:

trong đó \(x \bmod y\) là phần dư khi chia \(x\) cho \(y\). Hãy tìm và in ra \(p_1, p_2, \ldots, p_n\).

Dữ liệu vào

• Dòng đầu tiên chứa \(n\) — độ dài mảng (\(2 \le n \le 2 \times 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên phân biệt \(a_1, \ldots, a_n\) (\(1 \le a_i \le 3 \times 10^5\); \(a_i \ne a_j\) nếu \(i \ne j\)).

Dữ liệu ra

In ra \(n\) số nguyên \(p_1, p_2, \ldots, p_n\) (cách nhau bởi khoảng trắng).

Ví dụ

Input 1

4
6 2 7 3

Output 1

0 2 12 22

Input 2

3
3 2 1

Output 2

0 3 5