H - さいたまの矛盾 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

問題

SAITAMA (Secret Association of Ill-Temperedly Armored Massive Agents) は n 人の武装工作員からなる秘密組織である。 SAITAMAの各構成員には 1, 2, ..., n の固有の構成員番号が割り当てられている。 彼らはライバル組織であるGUNMA (Great Ultimate Nation of Massive Agents) を壊滅させるため、日夜鍛錬に明け暮れている。 それゆえ彼らは自身の組織内でのパワーランクについて常に気にかけており、彼らの交わす日常会話は「俺はあいつより強い」「私はB級1位だ。番号が50番以降の誰よりも強い」「奴は我らSAITAMAの中でも最弱」といった具合である。

SAITAMAの構成員の任意の2人の間には力関係が存在する。 ある2人の構成員 a, b について、a は b より強いか、a は b より弱いかのいずれかである。 この力関係、より厳密には、「より強い」関係と「より弱い」関係の2つは、推移律と非反射律を満たしている。 すなわち、3人の構成員 a, b, c について、a が b より強く、b が c より強いとき、必ず a は c より強いことになる。 また、a が a 自身より強いということはない。これらのことは「より弱い」関係についても同様である。

GUNMAのスパイでありSAITAMAの構成員たちの会話を盗聴していたAさんは、彼らの言いふらしている力関係に矛盾が含まれていることに気付いた。 しかし、SAITAMAは極めて多くの構成員からなる組織であるため、どの発言が矛盾を生んだのかはよくわからなかった。 もしかすると矛盾があったという認識すら思い違いであるかもしれない。

幸いAさんはSAITAMAの構成員たちの発言内容と発言順序を全て記憶していた。 奇妙なことに、彼らの発言は全て「番号 p の構成員は番号が l 以上 r 以下の誰よりも強い/弱い」という形式であったそうである。

なんとしてでも矛盾の原因を突き止めたいAさんは、SAITAMAの構成員たちの発言の中でそれまでの発言内容と矛盾する最初の発言をひとまず特定したいと考えている。 すなわち、時系列順に発言を並べたとき、1番目から k-1 番目までの発言の列には矛盾が含まれないが、1番目から k 番目までの発言の列には矛盾が含まれるような整数 k を特定したい。 あなたの仕事は、Aさんのために、SAITAMAの構成員たちの発言の中で最初に矛盾が発生するものが何番目であるかを求めることである。

入力

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

n m
p_1 c_1 l_1 r_1
p_2 c_2 l_2 r_2
:
p_m c_m l_m r_m
  1. 1行目には2つの整数 n と m が半角スペース区切りで与えられる。
    • n はSAITAMAの構成員の人数であり、1 ≦ n ≦ 1,000,000,000 を満たす。
    • m はSAITAMAの構成員たちの発言の数であり、1 ≦ m ≦ 1,000 を満たす。
  2. 2行目から m+1 行目までの m 行にはSAITAMAの構成員たちの発言に関する情報が時系列順に与えられる。
    • これらの行のうちの i 行目 (1 ≦ i ≦ m) には i 番目の発言の情報となる整数 p_i、文字 c_i、整数 l_i と整数 r_i が半角スペース区切りで与えられる。
    • i 番目の発言の情報の意味は以下の通りである。
      • c_i が s の場合、「番号 p_i の構成員は、番号が l_i 以上 r_i 以下であるどの番号の構成員より強い」ということを表す。
      • c_i が w の場合、「番号 p_i の構成員は、番号が l_i 以上 r_i 以下であるどの番号の構成員より弱い」ということを表す。
    • c_i は s か w のいずれかである。
    • p_i は 1 ≦ p_i ≦ n を満たし、l_i と r_i は 1 ≦ l_i ≦ r_i ≦ n を満たす。

出力

最初に矛盾が発生する発言の番号を1行に出力せよ。
矛盾がない場合、0 を1行に出力すること。
出力は標準出力に行い、最後には改行を出力すること。

入力例 1

4 5
4 w 1 3
3 w 2 2
2 s 3 4
3 s 1 1
1 s 2 2

出力例 1

5
  • 4番目の発言までは矛盾はありませんが、最後の発言が矛盾しています。
    • 4番目の発言までの情報で、構成員2は構成員3より強く、構成員3は構成員1より強いことがわかるので、推移律により構成員2は構成員1より強いことが言えます。
    • しかし、5番目の発言では構成員1は構成員2より強いとあり、これは矛盾です。

入力例 2

2 4
1 w 2 2
1 s 2 2
2 w 1 1
2 s 1 1

出力例 2

2
  • 構成員1が構成員2より弱く、かつ構成員1が構成員2より強いということはありえないので、2番目の発言は1番目の発言と矛盾しています。
  • 以降の発言にも矛盾がありますが、最初に矛盾する発言の番号である 2 が答えとなります。

入力例 3

1000000000 4
1 w 5 100000
1000000 s 100 888888
1000 w 10000 10000
1000000000 s 1 999999999

出力例 3

0
  • 矛盾はありません。番号の大小関係がそのまま力関係になっているようです。

出典

Maximum-Cup 2013