Giải bài trực tuyến

Mỗi người đều cố gắng tìm trong cuộc đời một sợi dây níu kéo họ với nụ cười, ý nghĩa và hy vọng. Có người gọi đó là hạnh phúc, có người định nghĩa đó là sự bình yên, lại có người đinh ninh rằng đó là tình yêu. Với Pirate, đó chỉ là đảo, dừa và chuối.

Thế mà ngày kia, lại có tên Cá Mập hung ác đang tâm đến lấy đi tất cả những thứ đó. Tên Cá Mập dùng hàm răng trắng không tì vết của mình để dọa Pirate rằng trong vòng ba ngày nếu không giao giấy tờ đảo cho hắn thì hắn sẽ cắn Pirate như cắn Pizza.

Chuyện đến nước này, Pirate chỉ biết tìm đến gặp Cá Mập Hơn, vốn là kình địch của Cá Mập (vì hắn mập hơn), để xin giúp đỡ. Tên này cũng chả tử tế gì nên cố tình làm khó dễ Pirate. Hắn ra cho Pirate một câu đố hóc hiểm, nếu trả lời được thì mới vác mỡ đến giúp. Câu đố như sau:

Giả sử rằng Pirate có N quả dừa. Quả dừa thứ i nặng A_i kí (A_i > 0). Pirate không hề biết trọng lượng của các quả dừa này. Với mỗi quả dừa i, Cá Mập Hơn sẽ tính tích (A_i - A_j) (với mọi 1 ≤ j ≤ N và j khác i). Hắn sẽ chỉ cho Pirate biết tích trên là số âm, số dương hay số 0 thông qua dãy kí tự B. Nhiệm vụ của Pirate là dựa vào dãy B để đoán ra trọng lượng của các quả dừa hoặc thông báo là dãy B không hợp lệ. Đặc biệt, dãy trọng lượng mà Pirate đoán ra phải có thứ tự từ điển nhỏ nhất. 

Dãy X₁, X₂, ..., X_N được gọi là có thứ tự từ điển nhỏ hơn dãy Y₁, Y₂, ..., Y_N nếu tồn tại k (1 ≤ k ≤ N) sao cho X₁ = Y₁, X₂ = Y₂, ..., X_{k - 1} = Y_{k - 1} và X_k < Y_k. 

Input

Input gồm nhiều dòng:

• Dòng thứ nhất ghi số T, số bộ test.
• T dòng tiếp theo: mỗi dòng là một dãy các kí tự liên tiếp nhau thể hiện một dãy B đã được mô tả trong đề bài. Kí tự thứ i là '+' nếu tích (A_i - A_j) (với mọi 1 ≤ j ≤ N và j khác i) là số dương, '-' nếu tích là số âm, '0' nếu tích bằng 0.

Output

Ouput gồm T dòng, mỗi dòng ghi ra một dãy số A có cùng số phần tử với dãy B tương ứng trong Input. Nếu không tồn tại dãy A thì in ra 'TIDAK MUNGKIN' (nghĩa là không tồn tại theo tiếng cá mập).

Example

Input:
2
+00
--
Output:
1 2 2
TIDAK MUNGKIN

Giới hạn

• 1 ≤ T ≤ 20.
• 2 ≤ N ≤ 30.
• Trong 25% số test có 2 ≤ N ≤ 8.