Коробки

У Мартина є $n$ коробок, пронумерованих натуральними числами від $1$ до $n$. У кожній коробці знаходиться іграшка. Іграшки також пронумеровані натуральними числами від $1$ до $n$ так, що спочатку іграшка з номером $i$ лежить у коробці з номером $i$.

Час від часу Мартин дзвонить одному зі своїх $m$ друзів, щоб той прийшов і поспілкувався. Під час зустрічі його друг дістає іграшки з коробок і починає гратися з ними. А поки Мартин більше цікавиться коробками. Коли стає нудно, друг повертає іграшки назад у коробки. Проте він не обов'язково кладе кожну іграшку в ту саму коробку, з якої вона була взята.

Мартин помітив, що кожен з його $m$ друзів щоразу перемішує іграшки однаково. Точніше, у кожного з його друзів є свій масив з $n$ цілих додатних чисел $p_1,...,p_n$, який визначає, як він буде складати іграшки назад у коробки. Кожне додатне ціле число від $1$ до $n$ зустрічається в цьому масиві рівно один раз. Його друг перемішує іграшки так, що в кінці зустрічі в коробці з номером $i$ опиняється іграшка, яка була в коробці з номером $p_i$ на початку зустрічі. Зверніть увагу: оскільки кожне додатне ціле число від $1$ до $n$ зустрічається в масиві рівно один раз, після того, як усі іграшки повернуться в коробки, у кожній коробці знову буде рівно одна іграшка.

Тепер Мартину цікаво відповісти на такі питання: чи може іграшка з номером $a$ (яка спочатку знаходиться в коробці з номером $a$) опинитися в коробці з номером $b$ в результаті послідовності зустрічей з його друзями. Послідовність зустрічей означає, що Мартин може дзвонити будь-яким друзям, яким хоче, і в будь-якому порядку. Він може дзвонити другу кілька разів або не дзвонити взагалі. Мартин зацікавлений у відповідях на $q$ таких питань.

Вхідні дані

У першому рядку записані натуральні числа $n,m(1\le n,m\le 1000)$ і $q(1\le q\le 5\cdot 10^5)$ — кількість коробок (і іграшок), кількість друзів Мартина та кількість питань відповідно.

У $k$-му з наступних $m$ рядків міститься масив цілих додатних чисел $p_1,...,p_n$, які $k$-й друг Мартина використовує для розкладання іграшок по коробках. Кожне додатне ціле число від $1$ до $n$ зустрічається в масиві рівно один раз.

Кожен з наступних $q$ рядків містить два натуральних числа $a$ і $b(1\le a,b\le n)$, що представляють питання.

Вихідні дані

У $q$ рядках виведіть відповіді на задані питання: TAK, якщо можна доставити розглядувану іграшку в потрібний ящик, і НІ в протилежному випадку.

Приклади