U333925 乒乓外交

本题背景根据真实事件改编。 “乒乓外交”是指1971年中国邀请美国乒乓球队访华，美国乒乓队成为自1949年以来获准进入中国的第一批美国人。此举被誉为“小球推动大球”，推动了中美关系正常化。时间来到了2021年，在国际乒联纪念“乒乓外交”50周年晚宴上，这次进过比赛组委会同意，中美跨国配对的混双球员可以搭配成组合来参加休斯敦世乒赛。

外界普遍猜测：两国选拔的不是最强组合，而是排名不算特别高的组合。已知美国队有$n$位球员，其中第$i$位的特点是$x[i]$；中国队有$m$位球员，其中第$j$位的特点是$y[j]$。每个球员的特点数字的二进制位是否为$1$或$0$代表该球员在特定的行为上是否存在特点。例如：是否夺得过奥运金牌，是否为左撇子，擅长横拍还是直拍，等等。 如果美国队的第$i$号球员和中国队的第$j$号球员搭配，该组合的实力值为$x[i]$ $xor$ $y[j]$。 备注：两个特点按位异或的效果，表示的是两者的互补程度，二进制位越高代表越重要。 现在有$p$个问询：美国队只考虑第$u$到第$d$号球员，中国队只考虑第$l$到第$r$号球员，其中各种组合里第$k$强的实力值为多少?

输入第一行包含两个正整数$n,m$。第二行包含n个非负整数$x[i]$，第三行包含m个非负整数$y[j]$， 特点数字均小于$2^{31}$。第四行包含一个正整数$p$，表示询问次数，随后$p$行，每行均包含5个正整数，用来描述一次询问，每行包含五个正整数$u,d,l,r,k$，含义如题意所述。 保证：$1

输出共$p$行，每行包含一个非负整数，表示此次询问的答案。