Задано подвешенное дерево, содержащее n (1 ≤ n ≤ 300000) вершин. Каждая вершина покрашена в один из n цветов. Требуется для каждой вершины v вычислить количество вершин с цветами в m (1 ≤ m ≤ 10) отрезках-запросах li, ri, встречающихся в поддереве с корнем v. Вершина лежит в отрезке, если номер её цвета c (li ≤ c ≤ ri).

Input

В первой строке задано числа n и m. Последующие n строк описывают вершины, по одной в строке. Описание очередной вершины i имеет вид pici, где pi - номер родителя вершины i, а ci - цвет вершины i (1 ≤ ci ≤ n). Для корня дерева pi = 0.

Следующие m строк содержат запросы в формате двух чисел li, ri (1 ≤ li ≤ ri ≤ n).

Output

Выведите n строк по m чисел, обозначающих количества цветов в поддеревьях с корнями в вершинах 1, ..., n в соответствующих отрезках.