构造部落
题号：NC312015
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}由于残暴的文字狱，后续题目名字“构造王国”等被迫改名。
\hspace{15pt}部落时代对于我们已经非常遥远了，因此部落时代的时间我们很难精确的描述。
\hspace{15pt}我们已知部落时代有 n 位首领，第 1 位部落首领在位的第 1 年为公元 s 年，还知道第 i 位首领在位时间 t_i，在此我们假设每一位首领的在位时间都恰好为整数年。n 位首领按编号顺序连续在位，即第 i 位首领在位结束后的次年，第 i+1 位首领立即即位。
\hspace{15pt}现在，考古学家发现了 q 件文物，每件文物上记录了在第 x 位首领在位的第 y 年发生的事件，你需要帮助考古学家确定每个事件发生在公元多少年。

输入描述:

\hspace{15pt}第一行输入三个整数 n,q,s \left(1 \leq n, q \leq 2 \times 10^5;\, -10^9 \leq s \leq 10^9\right)，表示部落首领数量，文物数量，第一位部落首领在位的第一年的公元年份。
\hspace{15pt}第二行输入 n 个正整数 t_1, t_2, \ldots, t_n \left(1 \leq t_i \leq 5 \times 10^3\right)，表示每一位首领在位的年数。
\hspace{15pt}此后 q 行，第 i 行输入两个整数 x_i, y_i \left(1 \leq x_i \leq n;\, 1 \leq y_i \leq t_{x_i}\right) 表示第 i 件文物记录的是第 x_i 位首领在位的第 y_i 年。

输出描述:

\hspace{15pt}对于每一件文物，新起一行输出一个整数，表示该事件发生在公元多少年。
示例1

输入

复制 
6 3 0
1 1 4 5 1 4
1 1
3 3
4 4

输出

复制 
0
4
9

说明

\hspace{15pt}在这个样例中：
\hspace{23pt}\bullet\,第一位首领在位的第 1 年为公元 0 年；
\hspace{23pt}\bullet\,第二位首领在位的第 1 年为公元 1 年；
\hspace{23pt}\bullet\,第三位首领在位的第 1 年为公元 2 年，在位的第 3 年为公元 4 年；
\hspace{23pt}\bullet\,第四位首领在位的第 1 年为公元 6 年，在位的第 4 年为公元 9 年。
示例2

输入

复制 
6 4 8
1 1 4 5 1 4
1 1
3 3
4 4
4 5

输出

复制 
8
12
17
18