У Мартина есть ящиков, помеченных натуральными числами от до . В каждой коробке лежит игрушка. Игрушки также помечены натуральными числами от до таким образом, что изначально игрушка с меткой находилась в коробке с меткой .
Время от времени Мартин звонит одному из своих друзей, чтобы тот пришел и пообщался. Как только они встречаются, его друг достает игрушки из коробок и начинает веселиться с ними. А пока Мартина больше интересуют коробки. Когда становится скучно, его друг убирает игрушки обратно в коробки. Однако он не обязательно кладет каждую игрушку в коробку, из которой она была взята.
Мартин заметил, что каждый из его друзей каждый раз перемешивает игрушки одинаково. Точнее, у каждого из его друзей есть свой массив из целых положительных чисел , который определяет, как он будет складывать игрушки обратно в коробки. Каждое положительное целое число от до встречается в этом массиве ровно один раз. Его друг перемешивает игрушки так, что в конце встречи в коробке с меткой оказывается игрушка, которая была в коробке с меткой в начале встречи. Обратите внимание: поскольку каждое положительное целое число от до встречается в массиве ровно один раз, после того, как все игрушки вернутся в коробки, в каждой коробке снова будет ровно одна игрушка.
Теперь Мартину интересно ответить на следующие вопросы: может ли игрушка с меткой (которая изначально находится в коробке с меткой ) оказаться в коробке с меткой в результате последовательности встреч с его друзьями. Последовательность встреч означает, что Мартин может звонить любым друзьям, которым хочет, и в любом порядке. Он может звонить другу несколько раз или не звонить вообще. Мартин заинтересован в ответах на таких вопросов.
В первой строке записаны натуральные числа и — количество коробок (и игрушек), количество друзей Мартина и количество вопросов соответственно.
В -й из следующих строк содержится массив целых положительных чисел , которые -й друг Мартина использует для раскладывания игрушек по коробкам. Каждое положительное целое число от до встречается в массиве ровно один раз.
Каждая из следующих строк содержит два натуральных числа и , представляющих вопрос.
В строках выведите ответы на заданные вопросы: DA, если можно доставить рассматриваемую игрушку в нужный ящик, и NE в противном случае.