Problem Description

Consider the following two problems:

$\textbf{Sequence Covering Problems}$:

In this problem, you are given three non-negative integer sequences $a, b, c$ of length $n$ at the beginning. Each time, you may choose an interval $[l, r]$ with cost $b_l + c_r$, such that the minimum of $a_l, a_{l+1}, \cdots, a_r$ is not $0$, and then decrease all of $a_l, a_{l+1}, \cdots, a_r$ by $1$. The goal is to make all numbers in $a$ become $0$ with the minimum total cost.

$\textbf{Many Sequence Covering Problems}$:

Based on Sequence Covering Problems, you are additionally given two non-negative integer sequences $d, e$. Now you may perform the following operations any number of times: choose $i \in [1, n]$, pay cost $d_i$ to increase $b_i$ by $1$, or pay cost $e_i$ to increase $c_i$ by $1$. After all operations are finished, solve the Sequence Covering Problems for the modified sequences $b, c$. Let the answer of that problem be $P$, and let the total cost spent on the operations be $Q$. You need to maximize $P - Q$. If this value can be unbounded (infinite), output $\texttt{INF}$. Otherwise, output this maximum value.

Now you need to solve $\textbf{Many Many Sequence Covering Problems}$:

You are given five incomplete sequences $A, B, C, D, E$ of length $n$. It is defined that if $A_i \ge 0$, then the value of $A_i$ is fixed as given; otherwise, the value of $A_i$ can be any integer in $[0, -A_i]$. The same rule applies to sequences $B, C, D, E$.

You need to compute, over all possible completions, the sum of the corresponding answers of Many Sequence Covering Problems. Since the answer may be $\texttt{INF}$, you need to output separately: the sum of all answers (modulo $998244353$) over the cases where the answer is not $\texttt{INF}$, and the number of cases whose answer is $\texttt{INF}$. Since the results may be large, take all outputs modulo $998244353$.

Input Format

The first line contains an integer $n$ ($1 \le n \le 5000$), indicating the length of the sequences.

The second line contains $n$ integers $A_1, A_2, \ldots, A_n$ ($0 \le |A_i| \le 5000$).

The third line contains $n$ integers $B_1, B_2, \ldots, B_n$ ($0 \le |B_i| \le 5000$).

The fourth line contains $n$ integers $C_1, C_2, \ldots, C_n$ ($0 \le |C_i| \le 5000$).

The fifth line contains $n$ integers $D_1, D_2, \ldots, D_n$ ($0 \le |D_i| \le 5000$).

The sixth line contains $n$ integers $E_1, E_2, \ldots, E_n$ ($0 \le |E_i| \le 5000$).

Output Format

Output a single line containing two integers: the sum of all answers (modulo $998244353$) over the cases where the answer is not $\texttt{INF}$, and the number of cases where the answer is $\texttt{INF}$ (modulo $998244353$).

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

8 12

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

408 228

Hint

Translated by ChatGPT 5