当前没有测试数据。

题目描述

给定两个长度为 (N) 的正整数序列 (a,b)，以及一个正整数 (p)。

定义

[ f(i,j)=\left(\min_{i\le k\le j}a_k\right)(b_j-b_i). ]

有 (Q) 次询问，每次给定一个区间 ([l,r])，求

[ \left( \max_{l\le i\le j\le r}f(i,j) \right)\bmod p. ]

输入格式

第一行包含三个正整数 (N,q,p)。

第二行包含 (N) 个正整数，表示序列 (a)。

第三行包含 (N) 个正整数，表示序列 (b)。

接下来 (q) 行，每行包含两个正整数 (l,r)，表示一次询问。

输出格式

输出 (q) 行，每行一个整数，表示对应询问的答案。

数据范围

对于所有数据，保证：

[ N,Q\le 10^5, ]

[ a_i,b_i\le10^9, ]

[ p\le10^9, ]

[ l\le r\le N. ]