Migrated from Lutece 2936 养鱼艺术家

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag: 李超线段树 古老的东方住着一位德高望重的猫猫，他在自家大院里养了 $n$ 个鱼塘，分别编号为 $1, 2 ... n$。

适逢八十岁大寿，猫猫的 $m$ 个亲朋好友前来送礼（鱼），他们各自带了同一种类的若干条鱼，并将这些鱼放进了猫猫的鱼塘里。具体来说，对于第 $i$ 位客人，他带的鱼的种类用数字来表示为 $c_i$，鱼被放进了编号区间 $[l_i, r_i]$ 的鱼塘中，并且放进的数量呈等差数列，等差为 $d_i$，在第 $l_i$ 个鱼塘放进的鱼的数量为 $v_i$。

猫猫想要从一些鱼塘中挑出数量最多的鱼并吃掉，他会对你发出 $q$ 次询问，对于第 $i$ 次询问，他想知道区间编号 $[ql_i, qr_i]$ 的鱼塘中数量最多的鱼的数量及其种类（每次询问后猫猫并不会真的吃掉了鱼，即每个鱼塘每种鱼的数量保持不变）。

注意不要把“数量最多”理解成求和了，该询问下每一种类的鱼的数量相当于其在满足条件的每个鱼塘内的最大的数量（具体可参考样例）。

Input

第一行输入三个整数 $n$, $m$ 和 $q$，表示鱼塘的数量为 $n$，共有 $m$ 个客人来送礼，猫猫对你发出来了 $q$ 次询问。

接下来的 $m$ 行每行输入四个数，第 $i$ 行输入的五个数 $c_i$，$l_i$，$r_i$ ，$d_i$ 和 $v_i$，分别鱼的种类、放入的鱼塘区间、等差大小以及第 $l_i$ 个鱼塘中放入的鱼的数量。

最后 $q$ 行每行输入两个数字，第 $i$ 行输入的两个数 $ql_i$ 和 $qr_i$，表示猫猫询问的鱼塘的区间。

Output

输出共 $q$ 行，每行输出两个整数，分别表示数量最多的鱼的数量及其种类。若询问区间内没有鱼，则输出 "$0$ $0$"（不用输出引号）；若询问区间内有多种鱼的数量相同，则输出种类编号最小的那个。

Samples

6 3 4
1 1 4 1 1
1 3 5 1 2
2 1 3 -1 4
1 5
1 2
5 5
6 6

7 1
4 2
4 1
0 0

Constraints

$1 \leq n, m \leq 1 \times 10^5$，$1 \leq q \leq 2 \times 10^5$，$1 \leq c_i \leq 1 \times 10^5$，$-100 \leq d \leq 100$，$1 \leq v \leq 1000$，$1 \leq l \leq r \leq n$

输入数据均为整数，且保证任何一种鱼的加入数目均为正整数。

Resources

2023 UESTC ICPC Training for Data Structures