図: 問題の条件をみたすあみだくじの例
なつめは大のねこ好きである。なつめは今日も日課としている野良ねこのブラッシングをするために，いつも野良ねこが集まってくる校庭の一角に向かうことにした。
そのスポットに今日は n 匹のねこが集まってきた。なつめは全員をブラッシングしてやりたかったのだが，ちょうどそこに来る直前に突然用事が出来てしまい，時間的に一匹しかブラッシングしてやれないことになってしまった。ブラッシングはどのねこも楽しみにしているので，一匹だけやると他のねこが嫉妬してしまう。そこでねこたちを納得させるために，どのねこをブラッシングするかをあみだくじで決めることにした。
あみだくじは n 本の縦線とあらかじめ引いた m 本の横線からなる。横線はとなりあう2本の縦線をそれらと垂直になるように結ばなければならない。また，横線同士が端点を共有してはいけない。ある1本の縦線の下端には当たりのマークがつけてある。これらの条件を満たすあみだくじの例を図に示す（これらはサンプル入力の例と対応している）。
ねこたちはそれぞれ縦線の上端からどれか1つを選ぶ。そしてあみだくじを辿った結果，当たりをひいたねこが，今日のブラッシングをしてもらう権利を手に入れることができる，というルールである。なつめは早速あみだくじを作成した。縦線・横線・当たりを書き込み，横線が見えないように隠した。
いよいよねこたちに選んでもらおうという時になって，なつめは n 匹のねこの中に，普段は顔を見せない野良ねこのアクタガワがいることに気がついた。アクタガワはもう一ヶ月ほどブラッシングをしておらず，毛がごわごわしている。
なつめは他のねこたちには申し訳ないと思いながらも，ズルをしてアクタガワをブラッシングするように仕組むことにした。まず，ねこたちにそれぞれ普通通り縦線を選んでもらう。全員が選び終わったらなつめはこっそりといくつかの横線を追加し，アクタガワが当たるようにあみだくじを変更するのだ。
しかし，アクタガワが選んだ縦線によってはアクタガワを当たりにするために新たに引かなければならない横線が多すぎて，細工をしている間にねこたちに計画がバレてしまうかもしれない。そこでなつめはまずそれぞれの縦線について，アクタガワがそれを選んだ場合に何本の横線を引けば当たりにすることができるかを求めることにした。
なお，新たに引く横線も，となりあう2本の縦線をそれらと垂直に結ばなければならず，横線同士が端点を共有しないように引かなければならない。
入力データは以下の形式で与えられる。
入力の一行目には縦線の本数 n (1 ≤ n ≤ 100000)，すでに引かれている横線の本数 m (0 ≤ m ≤ 100000)，当たりの縦線の番号 k (1 ≤ k ≤ n) が与えられる。ここで，縦線の番号は，左から順に，1, 2, ..., n とする。
続く m 行には横線の情報が与えられる。各行は一つの横線の情報を表す二つの整数 h (1 ≤ h ≤ 1000000) 及び x (1 ≤ x ≤ n - 1) が与えられる。h は縦線の下端からの距離，x は横線によって結ばれる縦線のうち，左側の縦線の番号である。つまり，この横線は x 番目と x+1 番目の縦線を結ぶことになる。
なお、入力では横線は整数高さの位置にしか存在しないが、新たに追加する横棒の位置は必ずしも整数高さでなくてもよい。
n 行の文字列を出力せよ。 i (1 ≤ i ≤ n) 行目には，アクタガワが i 番目の縦線を選んだときに，アクタガワを当たりにするために追加する必要がある横線の最小本数を出力せよ。
3 2 1 20 1 10 2
5 7 3 70 1 60 4 50 2 40 4 30 1 20 3 10 2
1 0 1
4 2 1 10 1 10 3
1 0 1
1 0 1 1 2
0
1 0 1 2