Byteasar là một lập trình viên đang phát triển một trình soạn thảo văn bản mang tính cách mạng. Trình soạn thảo có hai loại thao tác: chỉnh sửa văn bản và hoàn tác các thao tác đã thực hiện. Một tính năng mới của nó là hoàn tác nhiều cấp.

Thao tác chỉnh sửa văn bản được coi là thao tác cấp \(0\). Thao tác hoàn tác cấp \(i\), với \(i=1,2,\ldots\), hoàn tác thao tác gần nhất chưa bị hoàn tác và có cấp không vượt quá \(i-1\). Chẳng hạn, hoàn tác cấp \(1\) chỉ có thể hoàn tác thao tác chỉnh sửa; còn hoàn tác cấp \(2\) có thể hoàn tác thao tác chỉnh sửa hoặc thao tác hoàn tác cấp \(1\), nhưng không thể hoàn tác các thao tác có cấp lớn hơn.

Cụ thể hơn, mỗi thao tác đã thực hiện có một trong hai trạng thái: đang có hiệu lực hoặc đã bị hoàn tác. Ngay sau khi thực hiện một thao tác \(X\), nó ở trạng thái đang có hiệu lực. Nếu \(X\) là thao tác hoàn tác cấp \(i\), ta tìm thao tác gần nhất đang có hiệu lực và có cấp không vượt quá \(i-1\), gọi là \(X_1\), rồi đổi trạng thái của \(X_1\) thành đã bị hoàn tác. Nếu \(X_1\) cũng là một thao tác hoàn tác, ta phải khôi phục hiệu lực của thao tác mà \(X_1\) từng hoàn tác, gọi là \(X_2\). Tiếp tục theo cách đó: mỗi khi trạng thái của một thao tác hoàn tác \(X_j\) thay đổi, trạng thái của thao tác \(X_{j+1}\) mà nó từng hoàn tác cũng phải đổi theo. Điều này có thể tiếp tục làm thay đổi trạng thái của các thao tác khác. Chuỗi thay đổi kết thúc khi gặp một thao tác chỉnh sửa.

Để đơn giản, nội dung hiện tại của trình soạn thảo được biểu diễn bằng một số nguyên \(s\), gọi là trạng thái trình soạn thảo. Ban đầu \(s=0\). Mỗi thao tác chỉnh sửa chỉ định trạng thái mà nó tạo ra. Trạng thái trình soạn thảo được xác định bởi thao tác chỉnh sửa gần nhất đang có hiệu lực; nếu không có thao tác chỉnh sửa nào đang có hiệu lực thì trạng thái là \(0\).

Hãy giúp Byteasar viết chương trình theo dõi trạng thái trình soạn thảo.

Dữ liệu vào

Dòng đầu chứa số nguyên dương \(n\), là số thao tác Byteasar thực hiện.

\(n\) dòng tiếp theo mô tả các thao tác theo thứ tự thực hiện. Dòng thứ \(i\) trong số đó chứa một số nguyên \(a_i\) (\(-n\le a_i\le n\), \(a_i\ne0\)):

• Nếu \(a_i>0\), đây là thao tác chỉnh sửa đặt trạng thái trình soạn thảo thành \(a_i\).
• Nếu \(a_i<0\), đây là thao tác hoàn tác cấp \(-a_i\).

Dữ liệu bảo đảm với mỗi thao tác hoàn tác, luôn tồn tại một thao tác đang có hiệu lực ở cấp nhỏ hơn để hoàn tác.

Dữ liệu ra

In \(n\) dòng. Dòng thứ \(i\) chứa một số nguyên là trạng thái trình soạn thảo sau khi thực hiện \(i\) thao tác đầu tiên trong dữ liệu vào.

Ràng buộc

• \(1\le n\le300\,000\).
• \(-n\le a_i\le n\) và \(a_i\ne0\) với mọi \(1\le i\le n\).

Phân nhóm

Ký hiệu \(E_s\) là thao tác chỉnh sửa đặt trạng thái thành \(s\), còn \(U_i\) là thao tác hoàn tác cấp \(i\).

1. 20 điểm: \(n\le5000\).
2. 15 điểm: \(n\le300\,000\) và chỉ có các thao tác chỉnh sửa \(E_i\) cùng thao tác hoàn tác cấp \(1\), \(U_1\).
3. 28 điểm: \(n\le300\,000\); chỉ giá trị cuối cùng trong dãy kết quả được chấm đúng sai. Tuy nhiên, vẫn phải in đủ \(n\) số và \(n-1\) số đầu phải là các số nguyên trong đoạn từ \(0\) đến \(n\).
4. 37 điểm: \(n\le300\,000\).

Ví dụ

11
1
2
5
-1
-1
-3
4
-2
-1
-1
1

1
2
5
2
1
2
4
2
1
0
1