でぶ

問題文

shojin 王国に住んでいるおばけさんは、でぶにならないよう気を付けつけて食事計画をしています。

shojin 王国には飲食店またはトレーニングジムが $n$ 店あり、$i$ 番目の店は $0 \le a_i$ なら 1 食 $a_i$ カロリーの食べ物のみを提供する飲食店で、$a_i < 0$ なら 1 回で $|a_i|$ カロリーを消費する運動をするトレーニングジムです。$i$ 番目の店を店 $i$ とします。

おばけさんの食事計画は正整数の組 $(l, r, x)$ からなります。食事計画では、おばけさんは $i = l, l+1, \dots, r-1, r$ の順に店 $i$ に訪れます。店 $l$ では $1$ 回食事または運動をします。しかし、おばけさんは店に訪れるたびに食欲が増してしまい、またその分運動も必要になるので、前の店の量の $x$ 倍の食事または運動をします。より厳密には、店 $i$ では、$x^{i-l}$ 回食べ物を食べるか、運動します。

以上より、おばけさんの最終的な摂取カロリーは次の式で表されます。 $$\sum_{i=l}^{r} a_i x^{i-l}$$

しかし、最終的な摂取カロリーが $x-k$ の倍数であるとき、またそのときに限り、おばけさんはでぶになってしまいます。ただし、ある整数 $A$ が $x-k$ の倍数であるとは、$A=(x-k)B$ なる整数 $B$ が存在することを言います。

$q$ クエリ与えられます。各クエリでは $l, r$ が与えられるので、おばけさんがでぶにならないような $x$ が存在するか判定してください。

制約

• $1 \le n, q \le 10^5$
• $2 \le k \le 10^{18}$
• $-10^{18} \le a_i \le 10^{18}$
• $1 \le l_i \le r_i \le n$
• 入力は全て整数。

入力

$n\ q\ k$
$a_1\ a_2\ \dots\ a_n$
$l_1\ r_1$
$l_2\ r_2$
$\vdots$
$l_q\ r_q$

出力

各クエリに対して、条件を満たす $x$ が存在する場合 Yes を、存在しない場合 No を出力してください。最後に改行してください。

サンプル

6 5 2
-4 -4 1 1 -2 1
1 1
1 4
5 6
6 6
1 6

Yes
No
No
Yes
No