Дерево у відрізку
Задано підвішене дерево, яке містить n (1 ≤ n ≤ 300000) вершин. Кожну з вершин пофарбовано в один з n кольорів. Потрібно для кожної вершини v обчислити кількість вершин з кольорами в m (1 ≤ m ≤ 10) відрізках-запитах l[i], r[i], які зустрічаються у піддереві з коренем v. Вершина лежить у відрізку, якщо номер її кольору c (l[i] ≤ c ≤ r[i]).
Вхідні дані
У першому рядку задано числа n та m. Наступні n рядків, які описують вершини, по одній у рядку. Опис чергової вершини i має вид p[i] c[i], де p[i] - номер батька вершини i, а c[i] - колір вершини i (1 ≤ c[i] ≤ n). Для кореня дерева p[i] = 0.
Наступні m рядків містять запити у форматі двох чисел l[i], r[i] (1 ≤ l[i] ≤ r[i] ≤ n).
Вихідні дані
Виведіть n рядків по m чисел, які позначають кількість кольлорів у піддеревах з коренями у вершинах 1, ..., n у відповідних відрізках.