An đang học về cấu trúc cây tìm kiếm nhị phân (BST). An muốn mô phỏng quá trình chèn từng giá trị vào một BST ban đầu rỗng. Với mỗi thao tác chèn, hãy in ra các nút trên đường đi từ gốc đến vị trí chèn.

Hãy giúp An viết chương trình mô phỏng quá trình này.

Định dạng đầu vào

• Dòng đầu chứa số nguyên dương \(N\) (\(1 \le N \le 10^3\)).
• Dòng thứ hai chứa \(N\) số nguyên dương phân biệt \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)) theo đúng thứ tự cần chèn vào BST.

Định dạng đầu ra

• Gồm \(N\) dòng, dòng thứ \(i\) in ra các giá trị trên đường đi từ gốc đến nút cha của nút chứa \(a_i\) (không bao gồm \(a_i\)), cách nhau bởi một khoảng trắng. Nếu \(a_i\) là nút đầu tiên (gốc), in ra \(ROOT\).

Ví dụ

Input:

5
5 3 7 2 4

Output:

ROOT
5
5
5 3
5 3

Giải thích:

• Chèn \(5\): là gốc nên in \(ROOT\).
• Chèn \(3\): đi qua \(5\).
• Chèn \(7\): đi qua \(5\).
• Chèn \(2\): đi qua \(5 \to 3\).
• Chèn \(4\): đi qua \(5 \to 3\).