表白计划

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

众所周知,程序员是种神奇的没有妹子的生物。
有一个很厉害的程序员Doge,他没有妹子。于是他将自己心仪的n个妹子编号为1到n,然后制定了m个表白计划在接下来的t天内向妹子表白,对于某一个计划,他会在计划的第L天到第R天向编号为x的妹子每天表白一次。由于计划很多,有些表白区间可能有重复,所以他有可能在某一天跟同一个妹子表白很多次。他每一次表白被拒绝后都会收到被表白的妹子亲手写的好人卡,毫无悬念,他每一次都能收到好人卡。
现在Doge想知道在某些时间段他收到了多少张好人卡,还有这个时间段哪个妹子没有给过他好人卡,如果有多个妹子没有给过,他想知道编号最小的是哪个妹子。然而他正忙于制定下一个表白计划,所以请你这个程序员来帮下解决下吧!(PS:不要在意各种奇怪的事情,程序员本来就是个神奇的生物。)

Input

题目有多组测试数据。
对于每一组测试数据,第一行有三个数n, m, t(1 <= n, m, t <= 80000),在接下来的m行里,每一行有三个数L, R, x (1 <= L <= R <= t, 1 <= x <= n)表示Doge将在第L天到第R天每天向第x个妹子表白一次。接下来一行有一个数Q(1 <= Q <= 80000),接下来有Q行询问。对于询问,我们规定一个特殊的数z,z初始为0。每次询问给你两个数L, R (1 <= L<=R<=t),表示询问的区间为第L+z天到第R+z天,如果R+z超过t的话,就把区间变为第t-(R-L)天到第t天。对于每次询问,需要求出这段区间内Doge收到的好人卡个数和没有给过Doge好人卡的最小的妹子编号,如果所有妹子都给了好人卡,那么编号为0,然后把编号赋值给z。

Output

对于每次询问,输出为一行以一个空格间隔的两个数,第一个数为好人卡个数,第二个数为妹子编号。

Sample Input

5 5 10
1 3 1
3 5 2
7 9 3
2 4 4
8 10 5
4
1 6
6 8
1 9
4 6

Sample Output

9 3
5 1
14 0
3 1

Hint

 

Source

2015年浙江理工大学校赛