怪物城有一個大型公園，該公園由若干個景點以及連接這些景點所在地點的單向道路組成，共有 $v$ 個景點，編號為 $1, 2, \cdots, v$，這些景點包含了 $n$ 個入口和 $1$ 個出口，編號 $1, 2, \cdots, n$ 的景點為入口，編號 $v$ 的景點為出口。公園內一共有 $e$ 條道路，第 $i$ 條道路的起點為景點 $a_i$，終點為景點 $b_i$。

每個景點 $i$ 都有一個標誌 $s_i$，這個標誌是 &、| 兩者之一。類似地，每條道路 $i$ 也有一個標誌 $t_i$，這個標誌是 &、|、~、<、> 五者之一。如果 $t_i$ 不等於 ~，那麼道路 $i$ 還有一個權值 $l_i$。

每天，有 $n$ 隻怪物組成一波進入公園。第 $i$ 天，初始生命值分別為 $h_{i,1}, h_{i,2}, \cdots, h_{i,n}$ 的 $n$ 隻怪物在同一時刻分別進入 $n$ 個入口 $1, 2, \cdots, n$，然後這些怪物將在公園內闖蕩。在每一分鐘內，每隻怪物將會分身成 $k$ 個生命值和分身前相同的怪物（$k$ 為以該怪物所在景點為起點的道路數），分別朝着 $k$ 條以該怪物所在景點為起點的道路前進。

一隻怪物通過一條道路恰好需要 $1$ 分鐘。生命值為 $h$ 的怪物通過道路 $i$ 之後生命值將變化為 $h'$，下表給出了變化關係。

表格中 $\mathrm{AND}, \mathrm{OR}, \mathrm{NOT}, \mathrm{SHL}, \mathrm{SHR}$ 分別對應了按位與、按位或、按位取反、按位左移、按位右移五種位運算。其中 $h, l_i$ 和 $h'$ 都是 $32$ 位無符號整數。對於 $\mathrm{AND}, \mathrm{OR}$ 運算，滿足 $0 \le l_i < 2^{32}$。對於 $\mathrm{SHL}, \mathrm{SHR}$ 運算，滿足 $0 \le l_i < 32$。

當生命值為 $h_1, h_2, \cdots, h_c$ 的多隻怪物在同一景點 $i$ 相遇時，它們會合體成一隻怪物，其生命值 $h'$ 等於 $h_1, h_2, \cdots, h_c$ 做 $s_i$ 運算的結果，即：若 $s_i$ 為 &，則合體後的怪物生命值 $h'=h_1\ \mathrm{AND}\ h_2\ \mathrm{AND}\ \cdots\ \mathrm{AND}\ h_c$；若 $s_i$ 為 |，則合體後的怪物生命值 $h'=h_1\ \mathrm{OR}\ h_2\ \mathrm{OR}\ \cdots\ \mathrm{OR}\ h_c$。之後，如果該怪物位於公園的出口，那麼它就會離開公園。每一波怪物中，第一隻離開公園的怪物被稱為 Winner。所有怪物初始生命值和 Winner 離開公園時的生命值都會被記錄下來。

一隻怪物死亡當且僅當以下幾種情況之一（死亡後的怪物永遠不會行動或參與合體）：

1. 沒有一條道路以該怪物所在景點為起點，且該怪物不在出口。
2. 該怪物的生命值為 $0$。這意味著怪物可能在道路上死亡或者在合體後瞬間死亡。
3. 從所有怪物進入公園到當前時刻超過了 $k$ 分鐘，其中 $k$ 為怪物的壽命。

你可以認為第 $i+1$ 天時，在第 $i$ 天進入的怪物均離開公園或死亡。

然而，$m$ 天之後，一場天災將這個公園嚴重破壞了。不過，怪物城希望根據這 $m$ 天的記錄重建這個公園，但這件事有些困難，於是他找到了你來幫忙——當然，只要你設計出任意一種能滿足 $m$ 天的所有記錄的方案就行了。

輸入格式

輸入第 $1$ 行包含 $3$ 個整數 $n, m, k$，分別表示每天進入的怪物個數、天數以及怪物的壽命。

第 $2$ 行至第 $2m+1$ 行為 $m$ 天的記錄。其中，第 $2i$ 行包含 $n$ 個整數 $h_{i,1}, h_{i,2}, \cdots, h_{i,n}$，表示第 $i$ 天的 $n$ 隻怪物進入公園時的初始生命值，第 $2i+1$ 行包含 $1$ 個整數 $w_i$，表示第 $i$ 天怪物的 Winner 離開公園時的生命值。數據保證每天均存在 Winner。

輸出格式

針對給定的 $10$ 個輸入文件 rebuild1.in ~ rebuild10.in，你需要分別提交你的輸出文件 rebuild1.out ~ rebuild10.out。

輸出第 $1$ 行包含 $2$ 個整數 $v, e$，分別表示景點數和道路數，$n < v \le 100$，$0 \le e \le 500$。

第 $2$ 行包含 $1$ 個長度為 $v$ 的字串 $s$，其中第 $i$ 個字元 $s_i$ 為 &、| 之一，表示第 $i$ 個景點的標誌。

第 $3$ 行至第 $e+2$ 行，每行描述一條道路。其中，第 $i+2$ 行四個數或字元 $a_i, b_i, t_i, l_i$，分別表示第 $i$ 條道路的起點、終點、標誌和權值。$1 \le a_i, b_i \le v$，標誌為 &、|、~、<、> 之一，特別地，當 $t_i$ 為 ~ 時，$l_i$ 並不會輸入。允許兩景點間連有多條道路，也允許存在起點和終點相同的道路。

輸出任意一種滿足要求的方案即可。數據保證存在這樣的方案。

範例

輸入格式 1

2 4 2
11 1
20
11 2
18
11 3
16
18 12
12

輸出格式 1

4 4
||&&
1 3 | 0
2 3 ~
2 4 & 12
3 4 < 1

說明

範例輸出為一種可能的公園重建方案。以第 $1$ 天的怪物為例：

一開始，有 $2$ 隻怪物，分別位於景點 $1, 2$，生命值分別為 $11, 1$。

第 $1$ 分鐘，景點 $1$ 的怪物沿道路進入景點 $3$，其生命值變為 $11\ \mathrm{OR}\ 0=11$；景點 $2$ 的怪物分身成 $2$ 隻怪物，一隻沿道路進入景點 $3$，其生命值變為 $\mathrm{NOT}\ 1=4294967294$，另一隻沿道路進入景點 $4$，其生命值變為 $1\ \mathrm{AND}\ 12=0$，因此該分身在進入景點前死亡。之後，位於景點 $3$ 的 $2$ 隻怪物合體成 $1$ 隻生命值為 $11\ \mathrm{AND}\ 4294967294=10$ 的怪物。此時僅景點 $3$ 有 $1$ 隻怪物。

第 $2$ 分鐘，景點 $3$ 的怪物沿道路進入景點 $4$，其生命值變為 $10\ \mathrm{SHL}\ 1=20$。景點 $4$ 為出口，所以接下來該怪物將離開公園，成為 Winner。

因此，該組怪物的 Winner 生命值為 $20$。

子任務及部分分

我們提供了 $10$ 個評分文件 rebuild1.ans ~ rebuild10.ans。每個評分文件共 $10$ 行，第 $i$ 行一個評分參數 $a_i$，具體意義將在下面給出。

每個測試點單獨評分。對於每個測試點，如果選手的輸出格式不合法，則得 $0$ 分。如果輸出合法，但 $m$ 條記錄中只有部分記錄被滿足，則你還可能獲得部分分。

在你的方案中，若滿足的記錄條數為 $x_{user}$，你的分數將會由下表給出：

若不符合表中所有條件，得 $0$ 分；若符合表中的多個條件，則取分數最高的。

如何測試你的輸出

在終端中先切換到該試題的目錄下：（Windows 使用者請使用 cmd）（假設你把輸入輸出文件、checker 什麼的都放在了 rebuild 這個資料夾下）

cd rebuild

我們提供 checker 這個工具來測試你的輸出文件是否是可接受的。使用這個工具的方法是，在終端中執行

./checker_linux64 <case_no>

其中 case_no 是測試數據的編號。例如

./checker_linux64 3

將測試 rebuild3.out 是否可以接受。（Windows 使用者請使用 checker_win32 3）（什麼你是 Windows 64 位元？放心吧可以執行 win32 應用程式的。）

當然我們有對應的 linux 32 位元版本：checker_linux32。如果 linux 使用者發現無法執行程式，請嘗試執行 chmod +x checker_linux64 或 chmod +x checker_linux32 後重試。

在你呼叫這個程式後，checker 將根據你給出的輸出文件給出測試的結果。

請不要隨便更改 in 文件，防止 checker 出現不可預知的錯誤。

另外，你還可以在終端中使用指令

./checker_linux64 –w <case_no>

以將測試點 <case_no> 中每天怪物行進過程中的位置和生命值輸出到文件 report.log 中。注意文件 report.log 可能很大，極端情況下文件大小約為 $150\texttt{MB}$。