Bi viết lên giấy các số từ ~1~ đến ~n~ tại các vị trí khác nhau nhưng theo chiều kim đồng hồ, sau đó nối chúng lại với nhau theo thứ tự ~1~->~2~, ~2~->~3~,..~(n-1)~->~n~, ~n~->~1~ tạo thành một hình đa giác và tô màu cho các cạnh bằng màu đỏ (1), màu đen (2), màu xanh (3).

Bi lại tiếp tục nối hai đỉnh bất kỳ và gọi là đường chéo của đa giác và cũng tô màu cho nó bằng ba màu trên.

Quá trình vẽ đường chéo thực hiện cho đến khi đa giác được phân thành các hình tam giác (không chồng lên nhau) và có các cạnh có các cạnh nằm trên các cạnh của đa giác hoặc các đường chéo bên trong của nó.

Sau một hồi thực hiện các thao tác trên Bi muốn các anh chị kiểm tra giúp trạng thái của hình vừa vẽ gồm:

• Đa giác không vẽ phẳng (nghĩa là các đường chéo cắt nhau).

• Đa giác vẽ phẳng được nhưng các tam giác không phải là tam giác có ba màu khác nhau.

• Đa giác vẽ phẳng và các tam giác được tạo ra đều có ba màu khác nhau trên ba cạnh.

Input

Dòng thứ nhất chứa số $T$ là số testcase thỏa ~1 \le T \le 10~.

Dòng thứ hai chứa số nguyên ~n~ thỏa ~4 \le n \le 2.10^5~.

Dòng thứ ba chứa một số nguyên gồm ~n~ chữ số biểu thị màu sắc của các cạnh đa giác. Chính xác thì chữ số đầu tiên thể hiện màu của cạnh ~(1, 2)~, chữ số thứ hai thể hiện màu của cạnh ~(2, 3)~, v.v. cho đến chữ số thứ ~n~ đại diện cho màu của cạnh ~(n, 1)~.

Mỗi dòng trong số ~n-3~ dòng tiếp theo chứa mô tả về một đường chéo có dạng <X Y C>, trong đó ~X~ và ~Y~ là các đỉnh đa giác và ~C~ là màu của đường chéo ~(1 \le X, Y \le N, 1 \le C \le 3)~. Mỗi dòng mô tả một đường chéo hợp lệ, tức là các đỉnh ~X~ và ~Y~ sẽ không trùng nhau cũng như không lân cận.

Output

Ứng với mỗi testcase in ra các thông điệp sau:

• Nếu đa giác không vẽ phẳng được in "invalid triangulation".

• Nếu đa giác vẽ phẳng được nhưng các tam giác không thỏa ba cạnh khác màu in "invalid coloring"

• Nếu thỏa mã in "correct".

Samples

Sample Input 1

1
7
1223121
1 3 3
3 5 1
5 7 3
7 3 2

Sample Output 1

correct

Sample Input 2

1
5
12113
1 3 3
2 5 2

Sample Output 2

invalid triangulation

Sample Input 3

1
4
1212
1 3 2

Sample Output 3

invalid coloring