Colored Polygon Triangulation Quality

Given a convex polygon with n vertices numbered in clockwise order from 1 to n, each edge is colored with one of three colors. In addition, a set of diagonals (each also colored with one of the three colors) is provided. These diagonals may or may not form a triangulation of the polygon. A triangulation is valid if:

• The number of diagonals is exactly n-3.
• Every diagonal connects two non-adjacent vertices (an edge of the polygon is not considered a diagonal) and no two diagonals intersect in the interior of the polygon.
• The added diagonals, together with the polygon edges, partition the polygon into exactly n-2 triangles.

A triangulation is considered extremely good if in every resulting triangle, the colors of its three sides (which may be polygon edges or diagonals) are all pairwise distinct. Formally, if we denote by \( c(u,v) \) the color of the edge connecting vertices \( u \) and \( v \), then for every triangle with vertices \( i, j, k \) (with \( i<j<k \)) having all three edges present, it must hold that

[ ; c(i,j) \neq c(j,k),\quad c(j,k) \neq c(i,k),\quad c(i,j) \neq c(i,k). ]

Your task is to determine whether the given set of diagonals forms a valid triangulation of the polygon and, if so, whether the triangulation is extremely good. Output one of the following strings exactly:

• Invalid triangulation — if the diagonals do not form a valid triangulation.
• Valid triangulation — if the triangulation is valid but not extremely good.
• Extremely good triangulation — if the triangulation is valid and every triangle has three sides of distinct colors.

inputFormat

The input is given as follows:

1. An integer n representing the number of vertices of the polygon ( n \ge 3 ).
2. A string of length n consisting of characters (e.g. 'R', 'G', 'B') representing the colors of the polygon's edges. The i-th character is the color of the edge connecting vertex i and vertex i+1 (with vertex n+1 taken as vertex 1).
3. An integer d representing the number of diagonals.
4. d lines follow, each containing two integers u and v (with 1-indexed vertices) and a character representing the color of the diagonal connecting vertices u and v. It is guaranteed that the two vertices are not adjacent in the polygon.

outputFormat

Output a single line which is one of the following strings exactly:

• Invalid triangulation
• Valid triangulation
• Extremely good triangulation

sample

5
RGBRG
1
2 4 G

Invalid triangulation