PCK研究所が運用するスーパーコンピュータ「エル」は、研究所外部の企業や大学などの依頼に応じて様々な計算を行っています。エルの使用には予約が必要で、予約の際は開始時刻と終了時刻を指定します。ただし、異なる予約が重複してはいけません。
新しい予約が、すでに存在する予約のどれかと重複するかを報告するプログラムを作成せよ。ただし、ある予約の終了時刻と、別の予約の開始時刻が同じ場合は重複しないと考えて良い。また、すべての時刻は、エルの運用開始からの経過分数で与えられる。
入力は以下の形式で与えられる。
a b N s_1 f_1 s_2 f_2 : s_N f_N
1行目に新しい予約の開始時刻 a と終了時刻 b (0 ≤ a < b ≤ 1000) が整数で与えられる。2行目にすでに存在する予約の数 N (0 ≤ N ≤ 100) が与えられる。続く N 行に、すでに存在する予約の開始時刻 s_i と終了時刻 f_i (0 ≤ s_i < f_i ≤ 1000) が整数で与えられる。すでに存在する予約どうしに重複は無い。
新しい予約がすでに存在する予約と重複するなら1、重複しないなら0 と、1 行に出力する。
5 7 3 1 4 4 5 7 10
0
3 7 3 7 10 1 4 4 5
1