这是一个交互式问题。

给定一个含有 $n$ 个顶点和 $m$ 条边的有向无环图（DAG），每条边都有一个关联的权值。

任意一对顶点 $s$ 和 $t$ 之间可能存在多条路径。我们定义一条路径的权值为该路径上所有边权值的乘积。设 $f(s, t, c)$ 表示将图中每条边的权值都乘以 $c$ 后，从 $s$ 到 $t$ 的所有不同路径的路径权值之和。由于结果可能非常大，$f(s, t, c)$ 将对 $998244353$ 取模。

小 M 会提前告知你该 DAG 的结构（不包括边权）。

你可以提供参数 $s$、$t$ 和 $c$，交互器将返回 $f(s, t, c)$ 的值。你最多允许进行 $999$ 次此类查询，以获取有关该图的某些信息。在若干次查询循环后，交互器将提供一个参数 $k$，你需要确定 $f(1, n, k)$ 的值。

输入格式

第一行包含两个正整数 $n$ 和 $m$（$1 \le n \le 1000$，$1 \le m \le 5000$），其中 $n$ 表示图中的顶点数，$m$ 表示边数。

接下来的 $m$ 行中，每行包含两个正整数 $x$ 和 $y$（$1 \le x, y \le 1000$），表示图中存在一条从顶点 $x$ 到顶点 $y$ 的有向边。保证该图是一个有向无环图（DAG）。

交互

对于每次查询，你需要以 ? s t c（$1 \le s, t \le n$，$0 \le c < 998244353$）的格式输出，其中 $s, t, c$ 均为整数，交互器将返回 $f(s, t, c)$ 的答案。

当你确信已有足够的信息来回答问题时，输出 !，交互器将返回一个整数参数 $k$（$0 \le k < 998244353$），这意味着你需要求出 $f(1, n, k)$ 的值。

你需要输出 $f(1, n, k)$ 的结果。

在打印查询或答案后，切记输出换行符并刷新输出缓冲区。否则，你将获得 Idleness Limit Exceeded 的评测结果。为此，请使用：

fflush(stdout) or cout.flush() in C++; System.out.flush() in Java; flush(output) in Pascal;
stdout.flush() in Python; see the documentation for other languages.

样例

输入样例 1

3 3
1 2
2 3
1 3
1
2
12
123

输出样例 1

? 1 2 1
? 2 3 1
? 1 3 1
!
31488