D. Defense of the ACM
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тёмные времена нависли над ACM-ом. Тысячи команд ACM-щиков вышли на защиту от нападения CTF-щиков. Всего имеется N команд, пронумерованных от 1 до N. Каждая команда, по традиции, состоит из трёх человек. Каждому человеку присвоили параметр ACM-овости, выраженный целым числом.

ACM-щики хотят создать армию, выбрав из каждой команды ровно по одному человеку так, чтобы суммарная ACM-овость была как можно больше, но при этом делилась нацело на число D.

Так как ACM-щики по своей натуре любят усложнять задачи не пойми зачем, они решили рассмотреть несколько отрезков [li, ri], составляя армию лишь из команд с номерами из этого отрезка.

Собственно, ваша команда отвечает за обработку этих запросов. На горизонте уже видны флаги, у вас осталось меньше пяти часов!

Входные данные

Первая строка содержит два целых числа N (1 ≤ N ≤ 50 000) и D (1 ≤ D ≤ 50).

В следующих N строках содержится описание каждой команды в виде трёх целых чисел. ACM-овость каждого человека является целым числом от 0 до 109.

Следующая строка содержит целое число M — количество отрезков (1 ≤ M ≤ 300 000).

В следующих M строках идёт описание каждого запроса в виде пары чисел li и ri (1 ≤ li ≤ ri ≤ N).

Выходные данные

На каждый отрезок выведите в отдельной строке максимальную сумму, которую можно на нём собрать. Если же сумму, делящуюся на D собрать невозможно, выведите «-1» (без кавычек).

Примеры
Входные данные
2 2
0 1 3
1 2 3
3
1 1
2 2
1 2
Выходные данные
0
2
6
Входные данные
3 3
0 3 6
1 4 7
1 2 3
4
1 1
1 2
1 3
2 2
Выходные данные
6
-1
15
-1