2121: 寻宝

题目描述


采蘑菇的小西佬找到了一张上古年间的藏宝图,上面画着m座连绵不断的山,他决定去地图上记载的地点探险,可当他到达时,他发现当地其实有n座山,并且由于年代久远有些山也改变了形状,他不能准确的找到地图上藏宝的地点,于是他决定从一些连续的山中随意选择一座山作为地图上的第一个点,当他选定了起点以后,若当前的山与地图上记载山的高度相同他就会继续前往下一座山,否则就停下来,直到他到达地图上的最后一座山位置。我们假设如果他经过了大于k座山他就能找到宝藏(如果第一座山高度就不相同,视为经过0座山),现在的问题就是他有多大的可能性找到宝藏。
题目共有q次询问,每次询问有两个整数l,r代表采蘑菇的小西佬选择的区间,并且会给出第一次询问的k,之后的每个询问的k按照下面的式子算出
k=(ans*10086+666)%x;

ans代表上一次询问的答案,x=min(m,r-l+1);

输入


第一行输入三个数n,m,k(1<=n,m,k<=1e5);

第二行输入n个数代表n座山的高度(1<=a[i]<=1e9)

第二行输入m个数代表m座山的高度(1<=b[i]<=1e9)

第四行输入一个数q;(1<=q<=1e5)

接下来每行输入两个整数l,r;(1<=l<=r<=n)

输出


对于每个询问请输出对应的概率,以逆元的形式输出(mod=1e9+7);

样例输入


7 5 1
1 3 2 1 3 5 4
1 3 5 4 6
2
3 5
2 4

样例输出


333333336
333333336

提示


对于第一个询问,k=1,以3为起点能走过0座山,以4为起点能走过4座山,以5为起点能走过0座山,所以大于k的有1个

对于第二个询问,k=(333333336*10086+666)%min(5,4-2+1)=0,以2为起点能走过0座山,以3为起点能走过0座山,以4为起点能走过4座山,所以大于k的有1个


浙江理工大学月赛2019年5月

来源/分类


浙江理工大学月赛

请先 登录 后评论
  • 0 关注
  • 0 收藏,538 浏览
  • 轩爸 提出于 2019-08-02 22:38

相似问题