ZUEBOJ

兄弟们，我起床了，一日之计在于晨呐 —— lyh 17:37

众所周知， lyh 每天都是早上 7 点 30 准时起床，从来没有睡过懒觉（才信），（lyh：没错，我从来不睡懒觉），那这就很奇怪了捏 \(￣▽￣)/

为什么 lyh 会在这个时间在群中发出这条信息呢？显然，lyh 一定是陷入了时间诅咒（可怕的时间诅咒会让被诅咒者的时间流逝速度和现实的时间流逝速度不同！！！）

善良如你，发现了 lyh 深陷时间诅咒之中怎能袖手旁观？那么，让我们一起开启拯救 lyh 大行动吧！

聪明如你，自然从来不打无准备的仗，必然是有必胜的把握，当然这一切的自信来源于你的强大的能力；能够改变时间的流逝速度！！！而身为施加邪恶诅咒的大坏蛋当然也不是无能之辈，它也有能力改变时间的流逝速度（不过严格弱于你的能力）。

高手如你，自然有高手的风度，你从来都是用最小的力气赢得胜利，也从来只会在每次敌人出手后出手，这样才能展现出高手的闲庭信步。

形式化来讲：

你将会获得长度为 n 的正整数数组 a, 数组的第 i 项 ai 代表着 lyh 第 i - 1 秒到第 i 秒这段时间下现实中会度过多少秒。

显然，所有 ai 的和等于实际上 lyh 度过的在现实层面下的时间。

而与此同时，在 lyh角度下 lyh 度过的时间是 n 秒。

之后你会得到一个正整数 k，代表着大坏蛋能够使某个 a_i 变成 a_i + k。

接下来你会获得一个整数 q，表示大坏蛋会出手 q 次。

之后 q 行，每行会得到两个整数 l, r。

对于每对 l, r，大坏蛋会使 a_l, a_l+1, ... , a_r 都加上 k，。为了应对大坏蛋的使坏，你会在整局选择一个正整数 m，使 a_l, a_l+1, ... , a_r 都除以 m 并向下取整。对于每对 l, r，你都会在大坏蛋的每次使坏后紧接着出手一次。

请输出满足的最小的 m。