最近，你的汽车进行了一次软件更新。现在，如果你使用转向灯次数过多，汽车就会关闭，并报告“缓冲区溢出”（buffer overflow），不管这意味着什么！不过好的一面是，你现在可以去参加“报废汽车保护大会”（Broken-down Automobile Preservation Convention, BAPC）了。

你得知这个消息太晚了，所以你必须尽快开车赶到那里！当然，你仍然必须遵守所有的交通规则。在每个交叉路口，无论该路口是否在所有方向上都有道路，你都必须遵守以下规则：

• 在交叉路口左转（或右转）时，必须开启左（或右）转向灯。
• 直行时，转向灯必须关闭。
• 不允许掉头，即你不能沿着来时的路往回开。

为了安全起见，你决定最多开启转向灯 $k$ 次。幸运的是，你仍然可以随时关闭它们。这看起来限制很大，但你做出了一个精明的观察：只要你保持转向灯开启（它们不会自动关闭），你就可以一直向同一个方向转弯。

道路网络由交叉路口以及连接它们的道路组成。道路总是从东、南、西、北四个基本方向之一开始和结束。此外，它们绝不会在同一个交叉路口开始和结束。例如，考虑样例 1 到 3，其可视化效果如图 B.1 所示。这些样例仅在 $k$ 的值上有所不同。

图 B.1：第一、第二和第三个样例输入的视觉表示。

为了简化导航，你假设通过每条道路所需的时间相同，即每条道路的长度都视为 1。请找出从你当前位置到 BAPC 的最短路线，并确保你开启转向灯的次数不超过 $k$ 次。从你当前的位置出发时，你可以向任何方向行驶，而无需使用转向灯。

输入格式

输入包含以下内容：

• 第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 5000$, $0 \le k \le 20$)，分别表示交叉路口的数量以及转向灯可以开启的最大次数。
• 接下来的 $n$ 行，其中第 $i$ 行包含四个整数 $v^n_i$、$v^e_i$、$v^s_i$ 和 $v^w_i$ ($0 \le v^n_i, v^e_i, v^s_i, v^w_i \le n$)，分别表示从交叉路口 $i$ 向北、向东、向南和向西行驶所能到达的交叉路口编号，若为 0 则表示该方向没有道路。

你从交叉路口 1 出发，BAPC 位于交叉路口 $n$。每个交叉路口 $i$ 到任何其他交叉路口 $j$ 最多只有一条道路。如果这条道路存在，那么交叉路口 $j$ 到交叉路口 $i$ 也恰好有一条道路。

输出格式

如果可以从交叉路口 1 行驶到 $n$，且开启转向灯的次数不超过 $k$ 次，则输出该最短路线的长度。否则，输出 “impossible”。

样例

输入样例 1

5 2
0 2 0 0
4 0 3 1
0 4 2 0
0 5 2 3
0 0 0 4

输出样例 1

3

输入样例 2

5 1
0 2 0 0
4 0 3 1
0 4 2 0
0 5 2 3
0 0 0 4

输出样例 2

4

输入样例 3

5 0
0 2 0 0
4 0 3 1
0 4 2 0
0 5 2 3
0 0 0 4

输出样例 3

impossible

输入样例 4

5 2
0 2 0 0
4 0 3 1
0 4 2 0
0 0 2 3
0 0 0 0

输出样例 4

impossible