100 #P1401. *【差分约束】判断不等式方程组是否有解

*【差分约束】判断不等式方程组是否有解

【题意】

nn 个变量 xix_i

mm 个关系式。每个关系式如以下两种形式之一:

  • i j lt d,表示 k=ii+j1xi<d\sum\limits_{k=i}^{i+j-1} x_i < d

  • i j gt d,表示 k=ii+j1xi>d\sum\limits_{k=i}^{i+j-1} x_i > d

问是否存在满足 mm 个关系的 x1x_1 ~ xnx_n

【输入格式】

多组数据。
第一行两个整数 n m(1n,m100)n \ m(1 \le n ,m \le 100)
下来 mm 个关系式。
n=0n=0时结束。

【输出格式】

若存在满足 mm 个关系的 x1x_1 ~ xnx_n,则输出 lamentable kingdom ,否则输出 successful conspiracy

【样例输入】

4 2
1 2 gt 0
2 2 lt 2
1 2
1 0 gt 0
1 0 lt 0
0

【样例输出】

lamentable kingdom
successful conspiracy