题目描述

小蓝正在做一道交互题。有一个未知的下标从 1 到 $m$ 的数组 $a$，小蓝每次可以进行一次询问 $(l, r, p, q)$，然后交互程序会返回 $ans$ 满足 $\min\limits_{l \leq x \leq r} a[x] - \max\limits_{p \leq y \leq q} a[y] \geq ans$。但小蓝很快就发现，因为 $ans$ 并不是精确的值，所以他永远也无法得到实际的数组元素的值。

给定小蓝的几次询问和交互程序的返回值，请你帮他求出 $\max\limits_{1 \leq x \leq m} a[x] - \min\limits_{1 \leq y \leq m} a[y]$ 的可能的最小值。

输入格式

输入的第一行包含两个正整数 $n, m$，用一个空格分隔，分别表示小蓝的询问次数和数组长度。

接下来 $n$ 行，每行包含五个正整数 $l_i, r_i, p_i, q_i, ans_i$，相邻整数之间使用一个空格分隔，表示第 $i$ 次小蓝询问及其结果，含义如问题描述所述。

输出格式

输出一行包含一个整数表示答案，即 $\max\limits_{1 \leq x \leq m} a[x] - \min\limits_{1 \leq y \leq m} a[y]$ 的可能的最小值，如果无解请输出 No Solution。

2 4
1 1 2 2 2
1 2 3 4 2

4

2 2
1 1 2 2 1
2 2 1 1 1

No Solution

提示

样例说明

• 对于样例 $1$，$a_1 - a_2 \geq 2$，$\min(a_1, a_2) - \max(a_3, a_4) \geq 2$。所以 $a_1 - a_3 \geq 4$，所以 $a_i$ 之间差值的最大值不会小于 $4$。
• 对于样例 $2$，$a_1 - a_2 \geq 1$，$a_2 - a_1 \geq 1$，这种情况显然是无解的。

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$m \leq 300$；
• 对于所有评测用例，$1 \leq n \leq 500$，$1 \leq m \leq 10000$，$-100000 \leq ans_i \leq 100000$，$1 \leq l_i, r_i, p_i, q_i \leq m$，$0 \leq q_i - p_i < 100$，$0 \leq r_i - l_i < 100$。