出题人懒得想题面了，直接把题丢给了你。
你手里有 nnn 个未知数，分别为 x1, x2, ..., xnx_1,\ x_2,\ ...,\ x_nx1, x2, ..., xn ，这些未知数之间需要满足 mmm 个条件，每个条件是以下三种形式之一：
其中 xa, xbx_a,\ x_bxa, xb 代表两个不同的未知数，ccc 代表一个常数。
你需要回答 qqq 次询问，每次询问给出两个正整数 a, ba,\ ba, b ，你需要计算出 max(xa−xb)max(x_a - x_b)max(xa−xb) 。
第一行两个正整数 n, m, qn,\ m,\ qn, m, q ，分别表示未知数的个数和条件的个数。
接下来 mmm 行，每行四个正整数 k, a, b, ck,\ a,\ b,\ ck, a, b, c ，表示一个条件。k=1k = 1k=1 时，xa≤xb+cx_a \le x_b + cxa≤xb+c ；k=2k = 2k=2 时，xa=xb+cx_a = x_b + cxa=xb+c ；k=3k = 3k=3 时，xa≥xb+cx_a \ge x_b + cxa≥xb+c 。
接下来 qqq 行，每行两个正整数 a, ba,\ ba, b ，表示一次询问。
对于每次询问输出一行，总共输出 qqq 行。
每行一个整数，表示 max(xa−xb)max(x_a - x_b)max(xa−xb) 。
数据保证每次询问一定有整数解。
3 3 2 1 1 2 0 1 2 3 1 3 3 1 2 1 2 1 3
0 -2
3 3 2 1 1 2 3 1 2 3 4 1 3 1 5 1 3 3 2
7 8
1≤n≤5001 \le n \le 5001≤n≤500
1≤m, q≤1041 \le m,\ q \le 10^41≤m, q≤104
1≤a, b≤n1 \le a,\ b \le n1≤a, b≤n
−105≤c≤105-10^5 \le c \le 10^5−105≤c≤105