Тёмные времена нависли над 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
