問題
埼玉(暴躁装甲特工秘密协会) n 由武装人员组成的秘密组织。 SAITAMA的每位成员都有 1, 2, ..., n 已被分配一个唯一的会员编号。 他们夜以继日地训练,以摧毁他们的竞争对手组织 GUNMA(大规模特工的伟大终极国家)。 因此,他们总是很在意自己在组织内的实力排名,每天的对话都是“我比那家伙强”、“我是B班第一,我比50岁以上的人都强”、“他是我们埼玉人中最弱的”之类的话。
SAITAMA 的任意两名成员之间都存在权力关系。 两名成员 a, b ,a 表示 b 更强或a 表示 b 要么更弱,要么更弱。 这些权力关系中的两种,或者更准确地说,“较强”和“较弱”关系,满足传递律和非自反律。 即3名成员 a, b, c ,a 是 b 更强,b 是 c 当更强时,总是 a 表示 c 会更强。 另外,a 是 a 没有人比自己更强。对于“较弱”的关系也是如此。
A先生是群马的间谍,在偷听埼玉成员的谈话时,注意到他们所谈论的权力关系存在矛盾。 不过,由于埼玉是一个由极其庞大的成员组成的组织,因此尚不清楚究竟是哪一种说法引起了矛盾。 甚至认为存在矛盾的看法也可能是一种误解。
幸运的是,A先生记住了SAITAMA成员所说的一切以及他们说的顺序。 奇怪的是,他们只说“不。 p 的成员编号为 l 以上 r 似乎是“比下面的任何人都强/弱”的形式。
A先生不惜一切代价想要找出矛盾的原因,他想找出SAITAMA成员的第一个与之前的声明相矛盾的声明。 换句话说,当话语按时间顺序排列时,从第一个开始 直到 k-1 的语句序列不包含任何矛盾,但是 一个整数,使得直到 k 的语句序列包含矛盾。 我想识别 k 。 你的任务是为A先生找出埼玉成员发表的最先出现矛盾的言论的数量。
入力
输入将以以下格式从标准输入提供。
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
- 第一行两个整数 n 和 m 由半角空格分隔。
- n 是 SAITAMA 的会员数量,1 ≦ n ≦ 1,000,000,000 很满意。
- m 是 SAITAMA 成员发表的言论数量,1 ≦ m ≦ 1,000 很满意。
- 从第二行开始 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 是
- c_i 表示
s或w。 - p_i 表示 1 ≦ p_i ≦ n 很满意,l_i 和 r_i 表示 1 ≦ l_i ≦ r_i ≦ n 很满意。
出力
如果没有矛盾的话, 在一行上输出
0 。 输出应为标准输出,并在末尾输出换行符。
入力例 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
- 到第四个陈述为止都没有矛盾,但最后一个陈述是矛盾的。
- 从到第四条语句的信息中,我们可以看到成员2强于成员3,成员3强于成员1,因此根据传递律我们可以说成员2强于成员1。
- 然而,第五条语句说成员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就是答案。
入力例 3
1000000000 4 1 w 5 100000 1000000 s 100 888888 1000 w 10000 10000 1000000000 s 1 999999999
出力例 3
0
- 不存在矛盾。看来数字的大小关系和幂关系是一样的。