Consider the following two problems:

Sequence Covering Problems

Given three non-negative integer sequences $a, b, c$ of length $n$, you can perform the following operation any number of times:

• Choose an interval $[l, r]$ with cost $b_l + c_r$, such that the minimum value of $a_l, a_{l+1}, \dots, a_r$ is not $0$. Subtract $1$ from all elements $a_l, a_{l+1}, \dots, a_r$.

You need to make all numbers in $a$ equal to $0$ with the minimum total cost.

Many Sequence Covering Problems

Based on the Sequence Covering Problems, given two non-negative integer sequences $d, e$, you can now perform the following operation any number of times:

• Choose $i \in [1, n]$, and pay a cost of $d_i$ to increase $b_i$ by $1$, or pay a cost of $e_i$ to increase $c_i$ by $1$.

After all operations, solve the Sequence Covering Problems for the modified sequences $b$ and $c$. Let the answer be $P$ and the total cost of operations be $Q$. You need to maximize the value of $P - Q$. If this value can be infinitely large, output $\infty$; otherwise, provide this maximum value.

Now you need to solve the Many Many Sequence Covering Problems:

Many Many Sequence Covering Problems

Given five incomplete sequences $A, B, C, D, E$ of length $n$. If $A_i \ge 0$, the value of $A_i$ is given; otherwise, the value of $A_i$ is an integer in the range $[0, -A_i]$. The same applies to sequences $B, C, D, E$.

You need to find the sum of the answers to the corresponding Many Sequence Covering Problems over all possible cases. Since the answer can be $\infty$, you need to provide two results separately:

1. The sum of all answers when the answer is not $\infty$.
2. The number of cases where the corresponding answer is $\infty$.

Since the answers can be very large, please output the results modulo $998244353$.

Input

The first line contains an integer $n$ ($1 \le n \le 5000$), representing the length of the sequences. The second line contains $n$ integers $A_1, A_2, \dots, A_n$ ($0 \le |A_i| \le 5000$). The third line contains $n$ integers $B_1, B_2, \dots, B_n$ ($0 \le |B_i| \le 5000$). The fourth line contains $n$ integers $C_1, C_2, \dots, C_n$ ($0 \le |C_i| \le 5000$). The fifth line contains $n$ integers $D_1, D_2, \dots, D_n$ ($0 \le |D_i| \le 5000$). The sixth line contains $n$ integers $E_1, E_2, \dots, E_n$ ($0 \le |E_i| \le 5000$).

Output

Output a single line containing two integers, representing the sum of all answers (when not $\infty$) modulo $998244353$, and the number of cases where the answer is $\infty$ modulo $998244353$, respectively.

Examples

Input 1

2
1 1
1 2
2 1
-1 -1
-1 -1

Output 1

8 12

Input 2

3
-1 -2 2
1 3 0
-3 0 -2
1 -3 0
1 3 3

Output 2

408 228