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

Вхідні дані

У першому рядку задано числа n та m. Наступні n рядків, які описують вершини, по одній у рядку. Опис чергової вершини i має вид pici, де pi - номер батька вершини i, а ci - колір вершини i (1 ≤ ci ≤ n). Для кореня дерева pi = 0.

Наступні m рядків містять запити у форматі двох чисел li, ri (1 ≤ li ≤ ri ≤ n).

Вихідні дані

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