#677. 【NFLSPC #3】芳

题目类型:传统型 时间限制:3000 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

题目描述

这片大地在地图上被划分为$m$行$m$列。有$n$种不同的花,第$i$种花,生长在$[u_i,d_i]$行$[l_i,r_i]$列的区域内,芳香度为$x_i$。当不同的花混合在一起,它们的芳香度变为它们各自的芳香度的异或值。

有$q$只精灵来到了这片大地上。每只精灵可以在$[U_i,D_i]$行$[L_i,R_i]$列的区域内任意采集花朵,并与一支自己携带的芳香度为$X_i$的花朵做成花束。每只精灵都希望知道,自己能做出的花束的最大芳香度是多少?


异或

异或,也写作xor,对应C++中的^运算。a xor b的含义是先将a、b两个数按二进制展开,对应位相同该位运算结果就是$0$,否则是$1$,再把结果转换回十进制。例如$12 \mathrel{\mathrm{xor}} 5 = 9$。


输入格式

第一行,三个整数依次为 $n$,$m$和$q$。

接下来$n$行每行五个数字,依次为$u_i$,$l_i$,$d_i$,$r_i$,$x_i$。

接下来$q$行每行五个数字,依次为$U_i$,$L_i$,$D_i$,$R_i$,$X_i$。

输出格式

输出$q$行,每行一个整数,代表这只精灵能做出的花束的最大芳香度。


样例一

input

2 100 2
1 1 2 2 1
4 4 5 5 3
2 2 3 3 2
4 4 4 4 2

output

3
2

样例解释

第一只精灵可以选择采第一种花,芳香度为$3$;或者不采花,芳香度为$2$。

第二只精灵可以选择采第二种花,芳香度为$1$;或者不采花,芳香度为$2$。


限制与约定

  • subtask$1$($100$分):保证 $1 \leq n,m,q \leq 30000$,$1 \leq u_i,d_i,l_i,r_i,U_i,D_i,L_i,R_i \leq m$,$0 \leq x_i,X_i \leq 10^5$;

时间限制:$3\texttt{s}$

空间限制:$512\texttt{MB}$


by skyline