あみだくじは,東アジアでよく使われる抽選の方式である.
複数の人に,1 つずつ景品を割り当てたり,仕事を割り振ったりするのによく使われる.
図 B-1: あみだくじの例
図 B-1 があみだくじの例である (Sample Input の最初のデータセットに対応).
人数と同じ本数の縦線を平行に引く.
そして,いくつかの隣り合う縦線の間に何本かの横線を縦線に垂直に引く.
横線の本数や位置は任意だが,2 本の横線の端点が一致してはならない.
普通は多数の横線をランダムに引く.
あみだくじを使うときは,まず,縦線の下端に景品や仕事の名前を書く.
次に各参加者はそれぞれ違う縦線の上端を選ぶ.
そして,選んだ縦線を上端から下向きにたどっていく.
横線との T 字路に達したらその横線を通って反対側の縦線に移り,下に向かっての移動を続ける.
縦線の下端に達したら,そこに書いてある景品や仕事が与えられる.
縦線の上端 P を選んだ場合を図 B-2 に示す.
この場合,得られるのは R にある景品や仕事である.
図 B-2: P からの経路
仮に P を選んだ参加者が実は Q にあるものが欲しかったとしたら,それは叶っていない.
しかし,待ってほしい.
新設されたばかりの特別ルールによればこの望みは叶えられるかもしれない.
新ルールでは好きな場所に横線を 1 本だけ追加してよいのだ.
実際,図 B-3 のように横線 X を追加すれば Q に行けるではないか.
図 B-3: 横線を追加した後の経路
与えられたあみだくじに 1 本だけ横線を加えて,指定された縦線の上端から指定された縦線の下端に到達するようにするには,横線をどこに加えればよいかを答えるプログラムを書きなさい.
入力は複数のデータセットからなる.
各データセットは次の形式で表される.
n m p q
x1 ⋯ xm
データセット中の項目は,すべて正の整数である.
n は縦線の本数を表す.
m は元のあみだくじの横線の本数を表す.
左から p 番目の縦線の上端を選んだ参加者が,左から q 番目の縦線の下端に到達したいものとする.
2 ≤ n ≤ 50,m ≤ 500,p ≤ n,q ≤ n が成り立つと仮定してよい.
x1, …, xm は元のあみだくじの横線の位置を表す.
xk が上から k 番目の横線の位置である.
xk ≤ n − 1 が成り立つ.
この横線は,左から xk 番目の縦線と xk + 1 番目の縦線を結んでいる.
この入力形式から,横線の上下方向の位置 (高さ) はすべて異なっていることが保証される.
入力の終わりは,4 つのゼロだけからなる行で表される.
入力中のデータセットの個数は 300 を超えない.