Tháp Tinh Thể

Bạn có một chuỗi gồm $n$ viên tinh thể. Loại của viên tinh thể thứ $i$ là $c_i$, một số nguyên từ $1$ đến $n$.

Bạn sẽ lần lượt đặt các viên tinh thể lên một lưới tọa độ vô hạn theo quy tắc sau:

• Ban đầu, bạn đặt viên tinh thể $1$ tại vị trí $(0, 0)$.
• Với mỗi $i$ ($2 ≤ i ≤ n$), nếu viên tinh thể thứ $i - 1$ được đặt tại vị trí $(x, y)$, thì viên tinh thể thứ $i$ có thể được đặt tại một trong các vị trí $(x + 1, y)$, $(x - 1, y)$, hoặc $(x, y + 1)$ (không được đặt tại vị trí $(x, y - 1)$), với điều kiện chưa từng có viên tinh thể nào được đặt tại vị trí đó trước đây.

Một tháp gồm $s$ viên tinh thể là tập hợp các viên tinh thể được đặt tại các vị trí $(x, y), (x, y + 1), ..., (x, y + s - 1)$ với một vị trí $(x, y)$ và số nguyên $s$ nào đó. Chiều cao của tháp là $s$, bằng số lượng viên tinh thể tạo nên nó. Một tháp loại $r$ là một tháp mà tất cả các viên tinh thể trong đó đều thuộc loại $r$.

Với mỗi loại $r$ từ $1$ đến $n$, hãy giải quyết bài toán sau một cách độc lập:

• Tìm chiều cao lớn nhất của tháp loại $r$ mà bạn có thể tạo ra bằng cách đặt các viên tinh thể theo đúng các quy tắc trên.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ($1 ≤ t ≤ 10^4$), biểu thị số lượng bộ thử nghiệm.

Mỗi bộ thử nghiệm gồm hai dòng:

• Dòng đầu tiên chứa một số nguyên $n$ ($1 ≤ n ≤ 10^5$), biểu thị số lượng viên tinh thể. Tổng của $n$ qua tất cả các bộ thử nghiệm không vượt quá $2 · 10^5$ ($\sum n ≤ 2 · 10^5$).
• Dòng thứ hai chứa $n$ số nguyên $c_1, c_2, ..., c_n$ ($1 ≤ c_i ≤ n$), biểu thị loại của các viên tinh thể.

Kết quả

Với mỗi bộ thử nghiệm, in ra $n$ số nguyên trên một dòng, phân tách bởi khoảng trắng. Số nguyên thứ $r$ ($1 ≤ r ≤ n$) là chiều cao lớn nhất của tháp loại $r$ có thể tạo thành. Nếu không thể tạo ra tháp nào thuộc loại $r$, số nguyên thứ $r$ phải là $0$.

Chấm điểm

Subtask 1 (30 points). $\sum n ≤ 50$

Subtask 2 (70 points). $1 ≤ t ≤ 10^4$; $1 ≤ n ≤ 10^5$; $\sum n ≤ 2 · 10^5$

Ví dụ

Input

6
7
1 2 3 1 2 3 1
6
4 2 2 2 4 4
1
1
5
5 4 5 3 5
6
3 3 3 1 3 3
8
1 2 3 4 4 3 2 1

Output

3 2 2 0 0 0 0
0 3 0 2 0 0
1
0 0 1 1 1
1 0 4 0 0 0
2 2 2 2 0 0 0 0

Ghi chú

Trong bộ thử nghiệm đầu tiên, một cách khả thi để tạo tháp thuộc loại $1$ có chiều cao $3$ là:

• Đặt viên tinh thể $1$ tại vị trí $(0, 0)$.
• Đặt viên tinh thể $2$ ở bên phải viên tinh thể $1$, tại vị trí $(1, 0)$.
• Đặt viên tinh thể $3$ ở phía trên viên tinh thể $2$, tại vị trí $(1, 1)$.
• Đặt viên tinh thể $4$ ở bên trái viên tinh thể $3$, tại vị trí $(0, 1)$.
• Đặt viên tinh thể $5$ ở bên trái viên tinh thể $4$, tại vị trí $(-1, 1)$.
• Đặt viên tinh thể $6$ ở phía trên viên tinh thể $5$, tại vị trí $(-1, 2)$.
• Đặt viên tinh thể $7$ ở bên phải viên tinh thể $6$, tại vị trí $(0, 2)$.

Các viên tinh thể tại các vị trí $(0, 0)$, $(0, 1)$, và $(0, 2)$ đều thuộc loại $1$, tạo thành một tháp có chiều cao $3$.

Trong bộ thử nghiệm thứ hai, chú ý rằng việc đặt viên tinh thể $6$ ở phía dưới viên tinh thể $5$ là không hợp lệ do quy tắc không cho phép đặt xuống phía dưới. Người ta chứng minh được rằng không thể tạo thành tháp thuộc loại $4$ có chiều cao $3$.