Ước chung lớn nhất của đa thức

Với hai đa thức $A(x)$ và $B(x)$ (trong đó $B(x)$ khác đa thức không), phép chia đa thức có dư cho ta biểu diễn duy nhất

$$A(x)=Q(x)·B(x)+R(x),\mathrm{deg}R<\mathrm{deg}B,$$

trong đó $R(x)$ được gọi là phần dư của phép chia $A(x)$ cho $B(x)$.

Nhờ phép chia có dư, ta định nghĩa được thuật toán Euclid tìm ước chung lớn nhất của hai đa thức: với cặp $(A,B)$, nếu $B$ là đa thức không thì kết quả là $A$; ngược lại kết quả là giá trị thuật toán trả về cho cặp $(B,R)$ với $R$ là phần dư của $A$ chia $B$. Mỗi lần chuyển từ cặp $(A,B)$ sang cặp $(B,R)$ được tính là một bước.

Cho số nguyên $n$. Hãy xây dựng hai đa thức thỏa mãn đồng thời:

• Bậc của mỗi đa thức không vượt quá $n$.
• Mọi hệ số đều là số nguyên có giá trị tuyệt đối không vượt quá $1$, tức thuộc $\{-1,0,1\}$.
• Hệ số cao nhất (hệ số của lũy thừa lớn nhất) của mỗi đa thức bằng $1$.
• Bậc của đa thức thứ nhất lớn hơn bậc của đa thức thứ hai.
• Thuật toán Euclid mô tả ở trên thực hiện đúng $n$ bước với cặp đa thức này.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $n$: số bước cần đạt được.

Dữ liệu ra

In ra hai đa thức, mỗi đa thức gồm hai dòng:

• Dòng thứ nhất chứa số nguyên $m$ ($0\le m\le n$): bậc của đa thức.
• Dòng thứ hai chứa $m+1$ số nguyên thuộc $\{-1,0,1\}$: các hệ số theo thứ tự từ hệ số tự do đến hệ số cao nhất.

Đa thức thứ nhất in trước, đa thức thứ hai in sau. Nếu không tồn tại đáp án, in ra $-1$. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

• $1\le n\le 150$

Ví dụ