小y有n个背包，每个背包里面有m个物品，每个物品价值v_i,j(0≤vi,j≤1e6)每个背包有一个下限li和一个上限ri，代表该个背包选的物品数$t$满足1≤l_i≤t≤r_i≤m因为小y是一个魔法师，有最多$k$次机会，使得价值为$x$的物品变为$2\ast x$（每个物品只能用一次） 询问对于每个合法的$P$，取$P$个物品的情况下总价值和最大是多少

易知[∑_i=1ⁿl_i,∑_i=1ⁿr_i]之间的$P$都合法

多组询问，对于每组询问输出对于所有合法$P$的答案的异或和 (对于每个$P$可以认为重新进行游戏)

第一行一个正整数$T$，代表数据组数 接下来每组数据第一行三个数代表$n,m,k$接下来n行m列，第i行第j列代表v_i,j最后n行每行两个数代表l_i,r_i$T\le 100$$n\le 500,m\le 500,0\le k\le 1e9$

保证除5组以外$n\le 50,m\le 50$