畀定兩個長度為 $n$ 嘅整數序列 $B=[b_1,\ldots,b_n]$、$C=[c_1,\ldots,c_n]$。對於長度為 $n$ 嘅非負整數序列 $D=[d_1,\ldots,d_n]$，設 $S(D)$ 係所有滿足 $d_i=0$ 嘅下標 $i$ 所組成嘅集合，定義 $f(D)=\sum_{i\in S(D)}b_i$、$g(D)=\prod_{i\in S(D)}c_i$。特別地，如果 $S(D)$ 係空集，則 $f(D)=0$、$g(D)=1$。
小 L 有一個長度為 $n$ 嘅正整數序列 $A=[a_1,\ldots,a_n]$。小 L 可以對序列 $A$ 做以下修改：
- 揀序列 $A$ 嘅兩個相鄰下標 $i,j$（即 $1\le i,j\le n$ 而且 $|i-j|=1$），如果 $a_i\le a_j$，就將 $a_j$ 改做 $a_j-a_i$，同時將 $a_i$ 改做 $0$。
小 L 可以做任意多次修改操作，亦可以完全唔做修改。對於序列 $A$ 經以上修改操作可以得到嘅所有序列 $D$，小 L 想求出 $f(D)$ 嘅最大值同埋 $g(D)$ 嘅總和，請你幫佢求出呢兩個值。形式化噉講，記 $T(A)$ 為序列 $A$ 經以上修改操作可以得到嘅所有序列嘅集合，你需要求出 $\max_{D\in T(A)}f(D)$ 同埋 $\sum_{D\in T(A)}g(D)$。其中，由於 $\sum_{D\in T(A)}g(D)$ 可能較大，你只需要求出佢對 $1\,000\,000\,007$ 取模之後嘅結果。
輸入格式
由檔案 sequence.in 讀入數據。
本題包含多組測試數據。
輸入嘅第一行包含兩個非負整數 $c,t$，分別表示測試點編號同測試數據組數。$c=0$ 表示呢個測試點係樣例。
接落嚟依次輸入每組測試數據。對於每組測試數據：
第一行包含一個正整數 $n$，表示序列長度。
第二行包含 $n$ 個正整數 $a_1,\ldots,a_n$，表示序列 $A$。
第三行包含 $n$ 個整數 $b_1,\ldots,b_n$，表示序列 $B$。
第四行包含 $n$ 個正整數 $c_1,\ldots,c_n$，表示序列 $C$。
輸出格式
輸出到檔案 sequence.out。
對於每組測試數據，只輸出一行，當中包含兩個整數，分別表示 $\max_{D\in T(A)}f(D)$ 同埋 $\sum_{D\in T(A)}g(D)$ 對 $1\,000\,000\,007$ 取模之後嘅結果。注意：$\max_{D\in T(A)}f(D)$ 唔需要對 $1\,000\,000\,007$ 取模。
本題包含兩個小問，正確回答其中任意一個小問都可以攞到部分分數。具體評分規則請睇「評分方式」。
樣例
輸入 1
0 3 3 5 6 6 3 6 9 1 2 3 6 1 1 4 5 1 4 -1 1 -1 1 -2 2 1 1 1 1 1 1 8 4 2 4 2 2 2 4 4 -2 4 9 -3 4 8 7 8 1 1 1 1 1 1 1 1
輸出 1
15 10 1 18 37 48
解釋
呢個樣例一共包含三組測試數據。
對於第一組測試數據，可以得到以下 $4$ 個序列：
- $D=[5,6,6]$，$f(D)=0$，$g(D)=1$；
- $D=[0,1,6]$，$f(D)=3$，$g(D)=1$；
- $D=[5,0,0]$，$f(D)=6+9=15$，$g(D)=2\times3=6$；
- $D=[0,0,5]$，$f(D)=3+6=9$，$g(D)=1\times2=2$。
所以 $\max_{D\in T(A)}f(D)=\max\{0,3,15,9\}=15$，$\sum_{D\in T(A)}g(D)=1+1+6+2=10$。
樣例 2
見選手目錄下嘅 sequence/sequence2.in 同 sequence/sequence2.ans。
呢個樣例滿足測試點 $3,4$ 嘅限制條件。
樣例 3
見選手目錄下嘅 sequence/sequence3.in 同 sequence/sequence3.ans。
呢個樣例滿足測試點 $5,6$ 嘅限制條件。
樣例 4
見選手目錄下嘅 sequence/sequence4.in 同 sequence/sequence4.ans。
呢個樣例滿足測試點 $7$ 嘅限制條件。
樣例 5
見選手目錄下嘅 sequence/sequence5.in 同 sequence/sequence5.ans。
呢個樣例滿足測試點 $11,12$ 嘅限制條件。
樣例 6
見選手目錄下嘅 sequence/sequence6.in 同 sequence/sequence6.ans。
呢個樣例滿足測試點 $16\sim18$ 嘅限制條件。
數據範圍
設 $N$ 為單一測試點內所有測試數據嘅 $n$ 嘅總和。對於所有測試數據，保證：
- $1\le t\le20$；
- $1\le n\le5\,000$，$N\le4\times10^4$；
- 對於所有 $1\le i\le n$，都有 $1\le A_i\le10^9$；
- 對於所有 $1\le i\le n$，都有 $-10^9\le B_i\le10^9$；
- 對於所有 $1\le i\le n$，都有 $1\le C_i\le10^9$。
| 測試點編號 | $n\le$ | $N\le$ | 特殊性質 |
|---|---|---|---|
| $1,2$ | $8$ | $10^2$ | 無 |
| $3,4$ | $200$ | $400$ | B |
| $5,6$ | $200$ | $400$ | 無 |
| $7$ | $500$ | $10^3$ | A |
| $8\sim10$ | $500$ | $10^3$ | B |
| $11,12$ | $500$ | $10^3$ | 無 |
| $13$ | $3\,500$ | $3\times10^4$ | A |
| $14,15$ | $3\,500$ | $3\times10^4$ | B |
| $16\sim18$ | $3\,500$ | $3\times10^4$ | 無 |
| $19,20$ | $5\,000$ | $4\times10^4$ | 無 |
特殊性質 A：保證 $A_1=A_2=\cdots=A_n=1$。
特殊性質 B：保證對於所有 $1\le i\le n$，$A_i$ 都喺 $[1,10^9]$ 入面獨立均勻隨機生成。
評分方式
對於每個測試點：
- 正確回答所有測試數據嘅 $\max_{D\in T(A)}f(D)$，可以攞到呢個測試點 $40\%$ 嘅分數；
- 正確回答所有測試數據嘅 $\sum_{D\in T(A)}g(D)$ 對 $1\,000\,000\,007$ 取模之後嘅結果，可以攞到呢個測試點 $60\%$ 嘅分數。
注意：就算選手只回答咗其中一個問題，都需要按照輸出格式輸出兩個整數，分別對應兩個問題嘅答案。