Ми маємо простий неорієнтований граф із \(N\) вершинами та \(M\) ребрами.

Вершини пронумеровані \(1,\ldots,N\). Для кожного \(i=1,\ldots,M\), \(i\)-е ребро з’єднує вершину \(a_i\) і \(b_i\). Крім того, степінь кожної вершини не перевищує 3.

Для кожного \(i=1,\ldots,Q\) дайте відповідь на наступний запит.

• Знайти суму індексів вершин, відстані яких від вершини \(x_i\) не більше \(k_i\).

Обмеження

• \(1 \leq N \leq 1,5 \times 10^5\)
• \(0 \leq M \leq \min (\frac{N(N-1)}{2},\frac{3N}{2})\)
• \(1 \leq a_i \lt b_i \leq N\)
• \((a_i,b_i) \neq (a_j,b_j)\), якщо \(i \neq j\).
• Степінь кожної вершини в графі не перевищує 3.
• \(1 \leq Q \leq 1,5 \times 10^5\)
• \(1 \leq x_i \leq N\)
• \(0 \leq k_i \leq 3\)
• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить цілі числа \(N, M\)

Наступні  \(M\) рядків містять цілі числа \(a_i, b_i\)

Далі рядок містить ціле число \(Q\)

Наступні  \(Q\) рядків містять цілі числа \(x_i, k_i\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть \(Q\) рядків. У \(i\)-му рядку має бути відповідь на \(i\)-й запит

Примітка

До прикладу 1:

Для 1-го запиту єдиною вершиною, чия відстань від вершини 1 є не більше 1, є вершина 1, тому відповідь 1.

Для 2-го запиту вершини, відстань яких від вершини 2 не перевищує 2, є вершини 2, 3, 4, 5 і 6, тому відповіддю є їхня сума, 20.

Аналогічно можна відповісти на 3-й і наступні запити.

Приклад вхідних даних

6 5
2 3
3 4
3 5
5 6
2 6
7
1 1
2 2
2 0
2 3
4 1
6 0
4 3

Приклад вихідних даних

1
20
2
20
7
6
20