Роман посадил дерево из n вершин. В каждой вершине записана строчная английская буква. Вершина 1 является корнем дерева, у каждой из n - 1 оставшихся вершин есть предок в дереве, с которым вершина соединена ребром. Предком вершины i является вершина p_i, причём номер предка всегда меньше, чем номер вершины (то есть, p_i < i).

Глубина вершины — это количество вершин на пути по рёбрам от корня до v. В частности, глубина корня равна 1.

Скажем, что вершина u лежит в поддереве вершины v, если мы можем попасть из u в v, переходя из вершины в предка. В частности, вершина v лежит в своём поддереве.

Рома даёт вам m запросов, i-й из которых задаётся двумя числами v_i, h_i. Рассмотрим вершины, лежащие в поддереве v_i, и находящиеся на глубине h_i. Определите, можно ли из букв, записанных в этих вершинах, составить строку, являющуюся палиндромом? Буквы, записанные в вершинах, можно переставить в произвольном порядке для составления палиндрома.