Person in Charge

• SleepingCup

Problem Description

Given two integer sequences $B = [b_1, \ldots, b_n]$ and $C = [c_1, \ldots, c_n]$, each of length $n$. For a non-negative integer sequence $D = [d_1, \ldots, d_n]$ of length $n$, let $S(D)$ be the set of indices $i$ where $d_i = 0$. Define $f(D) = \sum_{i \in S(D)} b_i$ and $g(D) = \prod_{i \in S(D)} c_i$. Specifically, if $S(D)$ is empty, then $f(D) = 0$ and $g(D) = 1$.

Little L has a positive integer sequence $A = [a_1, \ldots, a_n]$ of length $n$. Little L can perform the following modifications on the sequence $A$:

• Choose two adjacent indices $i, j$ in $A$ (i.e., $1 \le i, j \le n$ and $|i - j| = 1$). If $a_i \le a_j$, then set $a_j$ to $a_j - a_i$ and set $a_i$ to $0$.

Little L can perform any number of such modifications or none at all. For all sequences $D$ that can be obtained from $A$ through these modifications, Little L wants to find the maximum value of $f(D)$ and the sum of $g(D)$. Formally, let $T(A)$ be the set of all sequences obtainable from $A$ through the above operations. You need to compute $\max_{D \in T(A)} f(D)$ and $\sum_{D \in T(A)} g(D)$. Since $\sum_{D \in T(A)} g(D)$ may be large, you only need to output its value modulo $1,000,000,007$.

Scoring

For each test case:

• Correctly answering $\max_{D \in T(A)} f(D)$ for all test data will earn $40\%$ of the points for that test case.
• Correctly answering $\sum_{D \in T(A)} g(D)$ modulo $1,000,000,007$ for all test data will earn $60\%$ of the points for that test case.

Attention: Even if a participant answers only one of the two questions, they must still output two integers in the specified format, corresponding to the answers for both questions.

Input Format

This problem contains multiple test cases.

The first line of input contains two non-negative integers $c, t$, representing the test case number and the number of test data sets. $c = 0$ indicates that the test case is a sample.

For each test data set:

• The first line contains a positive integer $n$, the length of the sequence.
• The second line contains $n$ positive integers $a_1, \ldots, a_n$, representing sequence $A$.
• The third line contains $n$ integers $b_1, \ldots, b_n$, representing sequence $B$.
• The fourth line contains $n$ positive integers $c_1, \ldots, c_n$, representing sequence $C$.

Output Format

For each test data set, output a single line containing two integers: the maximum value of $f(D)$ and the sum of $g(D)$ modulo $1,000,000,007$. Note: $\max_{D \in T(A)} f(D)$ does not need to be modulo $1,000,000,007$.

This problem consists of two sub-questions, and correctly answering either will earn partial points. For detailed scoring rules, refer to the [Scoring] section.

Samples

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

15 10
1 18
37 48

Sample 1 Explanation

This sample contains three test data sets.

For the first test data set, the following 4 sequences can be obtained:

• $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 \times 3 = 6$;
• $D = [0, 0, 5]$, $f(D) = 3 + 6 = 9$, $g(D) = 1 \times 2 = 2$.

Thus, $\max_{D \in T(A)} f(D) = \max\{0, 3, 15, 9\} = 15$, and $\sum_{D \in T(A)} g(D) = 1 + 1 + 6 + 2 = 10$.

Sample 2

See the files sequence/sequence2.in and sequence/sequence2.ans in the contestant directory.

This sample satisfies the constraints of test cases $3$ and $4$.

Sample 3

See the files sequence/sequence3.in and sequence/sequence3.ans in the contestant directory.

This sample satisfies the constraints of test cases $5$ and $6$.

Sample 4

See the files sequence/sequence4.in and sequence/sequence4.ans in the contestant directory.

This sample satisfies the constraints of test case $7$.

Sample 5

See the files sequence/sequence5.in and sequence/sequence5.ans in the contestant directory.

This sample satisfies the constraints of test cases $11$ and $12$.

Sample 6

See the files sequence/sequence6.in and sequence/sequence6.ans in the contestant directory.

This sample satisfies the constraints of test cases $16\sim 18$.

Data Range

Let $N$ be the sum of $n$ across all test data sets in a single test case. For all test data, the following guarantees hold:

• $1 \le t \le 20$;
• $1 \le n \le 5,000$, $N \le 4 \times 10^4$;
• For all $1 \le i \le n$, $1 \le A_i \le 10^9$;
• For all $1 \le i \le n$, $-10^9 \le B_i \le 10^9$;
• For all $1 \le i \le n$, $1 \le C_i \le 10^9$.

• Special Property A: $A_1 = A_2 = \cdots = A_n = 1$.
• Special Property B: For all $1 \le i \le n$, $A_i$ is generated independently and uniformly at random from $[1, 10^9]$.