Attention (14:48更新)

  • ケースに制約違反が確認されました。修正しました。誠にすみませんでした。

Story

🤖

matcharate君とtearate君で協力して、なんとかnum168君の要望を満たすことができました。そして、満足気にnum168君は帰っていきました。

matcharate君たちはまたキッチンに戻って仕事を始めました。すると、このキッチンロボットである "GT Robot" 君はこう言ってきました。

"Himaninattanode,watashitoisshonigamewosimashou."

よく聞くと、どうやら GT Robot は暇になったのでなんかゲームをしようと言っています。ロボットが暇になることがあるのでしょうか...?
仕方ないので、またmatcharate君はtearate君を道連れにしてゲームで遊ぶことになりました。

GT Robot は何かたくさんのカードを持ってきました。

"Konocardnonakakaramatcharategadecidesitaintegerninaruyouni,multiplesitekudasai."

よく聞いてみると、GT Robot が持ってきたカードを用いて...なんかゲームをするようです。しかしtearate君は耳がいいので、ある整数を決めて何か整数を新たに作る、とだけ聞こえました。

仕方ないので遊んであげることにしてあげ、さっそくmatcharate君は何か奇抜な光を放つ不思議なメモ帳を持ってきました。そしてtearate君と仲良くゲームを始めました。

問題

整数 L,R,KL,R,K が与えられます。今、テーブルの上には RL+1R-L+1 枚のカードがあり、それぞれ L,L+1,...,R1,RL,L+1,...,R-1,R11 つずつ書かれています。

また、matcharate君は今「11」 とだけ書かれたメモを持っています。このメモに対し、以下の操作を 11 回以上繰り返し行います。

  • まずテーブルに置いてあるカードから 11 枚選び、さらに正整数 kk を選ぶ。その後選んだカードに書かれている整数を aa 、現時点でメモに書かれた整数を mm として、mmm×akm\times a^k に書き換える。

操作後、matcharate君が持っているメモに書かれた整数が KK にすることができるような操作の仕方は存在しますか?

すなわち、操作後にメモに書かれた整数を xx として x=1×a1×a2×...×an=Kx=1\times a_1\times a_2\times ...\times a_n=K と表されるとき、
すべての i (1in)i\ (1\le i\le n) に対し ai{L,L+1,...,R1,R}a_i\in \{L,L+1,...,R-1,R\} が成り立つような (a1,a2,...,an)(a_1,a_2,...,a_n) の選び方が存在するか判定してください。

入力

入力は以下の形式で与えられる。

LLRRKK

制約

  • 106L<R106-10^6\le L\lt R\le 10^6
  • 106K106, K1-10^6\le K\le 10^6,\ K\neq 1
  • 入力はすべて整数

出力

メモに書かれた整数を KK にすることができるような操作の仕方が存在するなら Yes 、しないなら No を出力せよ。

入出力例

入力例1
3 10 21
出力例1
Yes

例えば次のように操作をすることがよいです。

  • 33 が書かれたカードを選び、k=1k=1 とする。この時 x=1×31=3x=1\times 3^1=3 となる。
  • 77 が書かれたカードを選び、k=1k=1 とする。この時 x=3×71=21x=3\times 7^1=21 となる。
入力例2
-2 5 -180
出力例2
Yes

例えば次のように操作をするとよいです。

  • 2-2 が書かれたカードを選び、k=1k=1 とする。この時 x=1×(2)1=2x=1\times (-2)^1=-2 となる。
  • 22 が書かれたカードを選び、k=1k=1 とする。この時 x=(2)×21=4x=(-2)\times 2^1=-4 となる。
  • 55 が書かれたカードを選び、k=1k=1 とする。この時 x=(4)×51=20x=(-4)\times 5^1=-20 となる。
  • 33 が書かれたカードを選び、k=2k=2 とする。この時 x=(20)×32=180x=(-20)\times 3^2=-180 となる。
入力例3
1 4 97
出力例3
No

そのような組み合わせは存在しません。

入力例4
1 3 3
出力例4
Yes

33 が書かれたカードを選び、そのまま xx33 を掛け合わせればよいです。

Submit


Go (1.21)