Задано дві цілочисельні послідовності довжини $n$: $B=[b_1,\ldots,b_n]$ і $C=[c_1,\ldots,c_n]$. Для послідовності невід'ємних цілих чисел $D=[d_1,\ldots,d_n]$ довжини $n$ позначимо через $S(D)$ множину всіх індексів $i$, для яких $d_i=0$, і визначимо $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 має послідовність додатних цілих чисел $A=[a_1,\ldots,a_n]$ довжини $n$. Він може змінювати її так:
- Вибрати два сусідні індекси $i,j$ послідовності $A$ (тобто $1\le i,j\le n$ і $|i-j|=1$). Якщо $a_i\le a_j$, замінити $a_j$ на $a_j-a_i$, а одночасно $a_i$ — на $0$.
小 L може виконати довільну кількість змін, зокрема жодної. Серед усіх послідовностей $D$, які можна отримати з $A$ такими операціями, він хоче знайти найбільше $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\le5000$, $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$ | $3500$ | $3\times10^4$ | A |
| $14,15$ | $3500$ | $3\times10^4$ | B |
| $16\sim18$ | $3500$ | $3\times10^4$ | Немає |
| $19,20$ | $5000$ | $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\%$ балів за тест.
Навіть якщо ви відповідаєте лише на одне питання, потрібно виводити два цілі числа відповідно до формату виводу — відповіді на обидва питання.