Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

“The world undergoes Photosynthesia

Transform endless anger to Ecstasia

Connect your nerves

To the system of Philosophiofantasia!”

Lại một buổi diễn tập nữa đã xong, và giờ là lúc momo trở về nhà và nghỉ ngơi!

Vốn từng là một sinh viên khoa học máy tính, momo có nhiều ý tưởng và món đồ chơi thú vị và độc đáo. Và lần này cũng thế.

Từ khi học Đại học, momo đã tự thiết kế cho mình một chuỗi đèn màu đặc biệt: chuỗi đèn có dạng một cây (ở đây, cây là một đồ thị vô hướng, liên thông và không có chu trình) với gốc là đèn số 1; mỗi đèn sẽ được mắc với tối đa 2 đèn ở phía dưới nó.

Bộ đèn của momo đặc biệt ở chỗ: momo chỉ có thể điều khiển trạng thái của những đèn mà phía dưới nó không có đèn nào được mắc (ta gọi là đèn ngọn); các đèn còn lại sẽ sáng hoặc không sáng theo nguyên tắc sau:

• Mỗi đèn mà chỉ mắc đúng 1 đèn ở dưới nó sẽ được dán nhãn “NOT”.
• Mỗi đèn mà chỉ mắc đúng 2 đèn ở dưới nó sẽ có thể được dán một trong các nhãn “AND”, “OR” hoặc “XOR”.
• Với đèn dán nhãn “NOT”, trạng thái của nó sẽ ngược với trạng thái của đèn ở phía dưới mà nó được mắc.
• Với đèn dán nhãn “AND”, đèn này chỉ sáng khi cả 2 đèn mắc phía dưới nó cùng sáng.
• Với đèn dán nhãn “OR”, đèn này chỉ sáng khi ít nhất 1 đèn mắc phía dưới nó sáng.
• Với đèn dán nhãn “XOR”, đèn này chỉ sáng khi có đúng 1 đèn mắc phía dưới nó sáng.

(Lưu ý: nếu đèn a có mắc đèn b ở dưới, đèn b lại có mắc đèn c ở dưới, thì a không được coi là mắc với đèn c - tức là ta chỉ xét các đèn mắc trực tiếp với nhau).

Momo muốn tìm hai kịch bản để đèn số 1 sáng: một kịch bản với thứ tự từ điển nhỏ nhất, một kịch bản với thứ tự từ điển lớn nhất. Bạn có thể giúp chị đại của chúng ta được chứ? :”>

Ở đây, một kịch bản được biểu diễn như sau: cho biết chuỗi đèn có k đèn ngọn (1 ≤ k < n), một kịch bản sẽ được biểu diễn dưới dạng chuỗi nhị phân gồm k ký tự, mỗi ký tự nhận một trong hai giá trị là ‘0’ hoặc ‘1’ (lần lượt biểu thị đèn không sáng hoặc sáng); ký tự thứ i biểu diễn cho đèn ngọn có số thứ tự nhỏ thứ i trong chuỗi.

Chuỗi A được coi là có thứ tự từ điển nhỏ hơn chuỗi B nếu tồn tại một giá trị i (1 ≤ i ≤ k) sao cho: A_j = B_j với mọi j < i và A_i < B_i.

Input

Dòng đầu tiên chứa một số nguyên n (2 ≤ n ≤ 4000) - số lượng đèn trong chuỗi của momo.

n dòng tiếp theo, mỗi dòng chứa thông tin của một đèn. Dòng thứ i sẽ có định dạng như sau:

Nếu đèn thứ i là một đèn ngọn, dòng chỉ chứa từ “INPUT” duy nhất.

Nếu không, ban đầu dòng sẽ chứa một từ là nhãn của đèn (“AND”/”OR”/”XOR”/”NOT”).

Nếu nhãn là “NOT”, phía sau sẽ là 1 số nguyên p thể hiện chỉ số của đèn được mắc vào nó.

Nếu không, phía sau sẽ là 2 số nguyên p1, p2 thể hiện chỉ số của hai đèn được mắc vào nó.

Giới hạn: 1 ≤ p, p1, p2 ≤ n; p ≠ n, p1 ≠ n, p2 ≠ n, p1 ≠ p2.

Dữ liệu đảm bảo chuỗi đèn thu được có dạng của một cây.

Output

In ra hai dòng: dòng thứ nhất là chuỗi nhị phân thể hiện kịch bản có thứ tự từ điển nhỏ nhất, dòng thứ hai là chuỗi nhị phân thể hiện kịch bản có thứ tự từ điển lớn nhất.

Đôi khi hai dòng này có thể giống nhau (nếu chỉ có một kịch bản duy nhất).

Example

Input:
10
AND 9 4
INPUT
INPUT
XOR 6 5
AND 3 7
INPUT
NOT 10
INPUT
INPUT
AND 2 8

Output:
00101
11111