Let $G = (V, E)$ be an undirected graph. We call a function $c: V \to \mathbb{N}$ a coloring if for every edge $(u, v) \in E$, we have $c(u) \neq c(v)$.

A coloring $c$ is called nice if for every $v \in V$, we have $c(v) \in \{1, 2, \dots, k\}$. In other words, a coloring $c$ is nice if it uses only colors that are integers from $1$ to $k$.

A coloring $c$ is called smart if for every $v \in V$, there exists some $w \in V$ such that $w \neq v$ and $c(v) = c(w)$. In other words, a coloring $c$ is smart if every color used is used at least twice.

Bajtazar is looking for a suitable coloring for his graph. He once found a nice coloring $c_l$, but it seemed too simple and not ambitious enough. Another time, he managed to find a smart coloring $c_m$, but after some time, he could no longer stand looking at it.

Bajtazar has lost hope of ever encountering a coloring that is both nice and smart. Can you surprise him and find such a coloring?

Input

The first line of input contains three integers $n, m, k$ ($1 \le k \le n \le 200\,000$, $0 \le m \le 200\,000$). The number $k$ describes which colorings we consider nice, and $n$ and $m$ are the number of vertices and edges of Bajtazar's graph, respectively. The vertices of the graph are numbered from $1$ to $n$.

The next $m$ lines describe the edges of Bajtazar's graph. The $i$-th of these lines contains two integers $u_i, v_i$ ($1 \le u_i < v_i \le n$), meaning that vertices numbered $u_i$ and $v_i$ are connected by an edge. No pair $(u_i, v_i)$ will be repeated in the input.

The next two lines contain descriptions of the colorings $c_l$ and $c_m$, respectively. A description of a coloring consists of $n$ positive integers not greater than $n$: the $i$-th of these numbers is the color of the vertex numbered $i$.

The coloring $c_l$ is nice, and the coloring $c_m$ is smart.

Output

If there exists a coloring of the graph that is both smart and nice, you should print the word TAK in the first line of the output, and $n$ integers describing such a coloring in the second line. The description should be in the same format as the descriptions of the colorings given in the input.

If no such coloring exists, you should print the word NIE in the only line of the output.

Examples

Input 1

8 7 3
1 2
2 3
3 4
1 5
1 6
1 7
1 8
1 2 3 2 2 2 2 2
1 2 4 1 2 3 4 3

Output 1

TAK
1 2 1 2 3 3 3 3