题目描述

设有 $n$ 个未知数 $x_1, x_2,\dots,x_n$，它们需要满足以下全部约束条件：

• 数值随下标递增：$x_1\leq x_2\leq\cdots\leq x_n$；
• 一些未知数之间的差小于或等于某些给定的值；
• 一些未知数之间的差大于或等于某些给定的值；

请判定满足这些约束条件的解是否存在，如果存在，求出 $x_n-x_1$ 的上界与下界。

输入格式

第一行：两个正整数 $n$ 和 $m$； 第二行到第 $m+1$ 行：每行表示一个约束条件，首先有两个正整数 $i$ 和 $j$ 表示两个未知数的下标，保证 $i>j$，其次为一个 < 或 > 字符表示约束条件的类型，最后 有一个正整数 $b$ 表示该约束条件的界：

• 若约束条件类型为 <，表示条件为 $x_i-x_j\leq b$；
• 若约束条件类型为 >，表示条件为 $x_i-x_j\geq b$；

输出格式

• 若无解，输出 No solution，否则：
  • 在第一行输出 $x_n-x_1$ 的最大值，若不存在，输出 No upper bound；
  • 在第二行输出 $x_n-x_1$ 的最小值。

3 2
3 2 < 10
2 1 < 15

25
0

样例解释 1

0作为下界是因为未知数总满足xn-x1>=0

4 3
4 3 > 10 
2 1 > 20
4 1 < 25

No solution

样例解释 2

由前两个条件，x4与x1之间至少需要30，这与最后一个条件矛盾了

4 3
4 2 > 10 
3 1 > 20
4 1 < 25

25
20

数据范围

• 对于 $30\%$ 的数据，$2\leq n\leq 20$，$1\leq m\leq 200$；
• 对于 $100\%$ 的数据，$2\leq n\leq 2000$，$1\leq m\leq 5000$；
• $1\leq b\leq 10^9$