Traveler's Escape
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述


\hspace{15pt}\hspace{15pt}\hspace{15pt}\hspace{15pt}\hspace{15pt}

\hspace{15pt}旅行者偷走了芙宁娜最爱的甜点。此时，芙宁娜正在由 n 行 m 列方格组成的枫丹国内内四处搜捕他。方格以从上到下 1,2,\dots,n 行、从左到右 1,2,\dots,m 列编号。初始时刻为 1，旅行者位于左上角格子 (1,1)，他的目标是在大门关闭前到达右下角格子 (n,m) 从而逃离枫丹国。旅行者的移动规则如下：
\hspace{23pt}\bullet\,在每一个时刻，他只能沿向下或向右选择一个方向移动，并可以一次前进任意正整数步；移动完成后，时刻加 1。

\hspace{15pt}芙宁娜派出了 q 名检查官，第 i 名检查官将在时刻 t_i 占据格子 (x_i,y_i) 并一直驻守。无论旅行者在时刻 \tau\,(\tau\geqq t_i)：
\hspace{23pt}\bullet\,到达该格子；
\hspace{23pt}\bullet\,经过该格子；
\hspace{23pt}\bullet\,离开该格子，

\hspace{15pt}他都会立即被捕获，从而导致逃脱失败。此外，在时刻 k 之后大门将被永久关闭，若旅行者到达 (n,m) 时时刻已经大于 k，则同样逃脱失败。

\hspace{15pt}请你帮助旅行者计算：
{\hspace{20pt}}_\texttt{1.}\,在所有合法方案中逃离所需的最短时间；
{\hspace{20pt}}_\texttt{2.}\,在模 998\,244\,353 意义下，可以逃脱的总方案数量。

输入描述:

\hspace{15pt}本题包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq5\right) 代表数据组数，每组测试数据描述如下：

\hspace{23pt}\bullet\,一行四个整数 n,m,q,k\left(2\leqq n,m\leqq500;\ 1\leqq q\leqq100;\ 1\leqq k\leqq100\right)；
\hspace{23pt}\bullet\,此后 q 行，第 i 行输入三个整数 x_i,y_i,t_i\left(1\leqq x_i\leqq n;\ 1\leqq y_i\leqq m;\ 1\leqq t_i\leqq k\right)――第 i 名检查官的坐标及出现时刻。

\hspace{15pt}此外，数据保证 (1,1) 和 (n,m) 两格不会有检查官出现，但是可能会出现很多检察官出现在同一个格子的情况。

输出描述:

\hspace{15pt}对于每组测试数据：
\hspace{23pt}\bullet\,若 Traveler 无论如何都无法逃脱，输出一行-1；
\hspace{23pt}\bullet\,否则输出两个整数，依次为 方案数量（对 998\,244\,353 取模）与 最短时间。
示例1

输入

复制 
2
2 3 2 5
1 3 1
2 2 3
2 3 2 5
1 3 1
2 2 2

输出

复制 
1 2
-1

说明

约定：我们用 \text{T} 来代表旅行者的位置，数字代表对应时刻会出现的检察官，\text{F} 代表右下角的大门。

在第一个样例中，最短时间为 2，且仅存在一条合法路径（先向下再向右再向右）。





在第二个样例中，旅行者必被捕获，故输出 -1。



示例2

输入

复制 
1
8 8 11 8
7 4 2
3 1 2
1 8 1
2 1 1
5 4 1
5 8 3
8 5 4
7 1 1
3 6 1
7 2 1
1 7 2

输出

复制 
7763 3

备注: