Dane są dwa ciągi liczb całkowitych długości $n$: $B=[b_1,\ldots,b_n]$ oraz $C=[c_1,\ldots,c_n]$. Dla ciągu nieujemnych liczb całkowitych $D=[d_1,\ldots,d_n]$ długości $n$ niech $S(D)$ oznacza zbiór wszystkich indeksów $i$, dla których $d_i=0$. Definiujemy $f(D)=\sum_{i\in S(D)}b_i$ oraz $g(D)=\prod_{i\in S(D)}c_i$. W szczególności, jeśli $S(D)$ jest pusty, to $f(D)=0$ i $g(D)=1$.
小 L ma ciąg dodatnich liczb całkowitych $A=[a_1,\ldots,a_n]$ długości $n$. Może modyfikować go w następujący sposób:
- Wybiera dwa sąsiednie indeksy $i,j$ ciągu $A$ (czyli $1\le i,j\le n$ i $|i-j|=1$). Jeśli $a_i\le a_j$, zastępuje $a_j$ przez $a_j-a_i$, a jednocześnie $a_i$ przez $0$.
小 L może wykonać dowolnie wiele takich operacji, a także nie wykonywać żadnej. Dla wszystkich ciągów $D$, które można otrzymać z $A$ w ten sposób, chce znaleźć największą wartość $f(D)$ oraz sumę wartości $g(D)$. Pomóż mu obliczyć obie wartości. Formalnie, niech $T(A)$ oznacza zbiór wszystkich ciągów, które można otrzymać z $A$ za pomocą tych operacji. Należy obliczyć $\max_{D\in T(A)}f(D)$ oraz $\sum_{D\in T(A)}g(D)$. Ponieważ $\sum_{D\in T(A)}g(D)$ może być duża, wystarczy podać jej resztę modulo $1\,000\,000\,007$.
Wejście
Dane należy odczytać z pliku sequence.in.
Dane wejściowe zawierają wiele zestawów testowych.
Pierwszy wiersz zawiera dwie nieujemne liczby całkowite $c,t$, oznaczające odpowiednio numer testu i liczbę zestawów danych. Wartość $c=0$ oznacza test przykładowy.
Następnie podawane są kolejne zestawy danych. Każdy z nich ma następującą postać:
Pierwszy wiersz zawiera dodatnią liczbę całkowitą $n$, oznaczającą długość ciągów.
Drugi wiersz zawiera $n$ dodatnich liczb całkowitych $a_1,\ldots,a_n$, opisujących ciąg $A$.
Trzeci wiersz zawiera $n$ liczb całkowitych $b_1,\ldots,b_n$, opisujących ciąg $B$.
Czwarty wiersz zawiera $n$ dodatnich liczb całkowitych $c_1,\ldots,c_n$, opisujących ciąg $C$.
Wyjście
Wyniki należy zapisać do pliku sequence.out.
Dla każdego zestawu danych wypisz dokładnie jeden wiersz z dwiema liczbami całkowitymi: $\max_{D\in T(A)}f(D)$ oraz resztą z dzielenia $\sum_{D\in T(A)}g(D)$ przez $1\,000\,000\,007$. Wartości $\max_{D\in T(A)}f(D)$ nie należy obliczać modulo $1\,000\,000\,007$.
Zadanie składa się z dwóch pytań. Poprawna odpowiedź na dowolne z nich pozwala zdobyć część punktów. Szczegółowe zasady znajdują się w sekcji „Podzadania”.
Przykład
Wejście 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
Wyjście 1
15 10 1 18 37 48
Uwagi
Przykład zawiera trzy zestawy danych.
W pierwszym zestawie można otrzymać następujące cztery ciągi:
- $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$.
Zatem $\max_{D\in T(A)}f(D)=\max\{0,3,15,9\}=15$, a $\sum_{D\in T(A)}g(D)=1+1+6+2=10$.
Przykład 2
Zobacz pliki sequence/sequence2.in oraz sequence/sequence2.ans w katalogu zawodnika.
Przykład spełnia ograniczenia testów $3,4$.
Przykład 3
Zobacz pliki sequence/sequence3.in oraz sequence/sequence3.ans w katalogu zawodnika.
Przykład spełnia ograniczenia testów $5,6$.
Przykład 4
Zobacz pliki sequence/sequence4.in oraz sequence/sequence4.ans w katalogu zawodnika.
Przykład spełnia ograniczenia testu $7$.
Przykład 5
Zobacz pliki sequence/sequence5.in oraz sequence/sequence5.ans w katalogu zawodnika.
Przykład spełnia ograniczenia testów $11,12$.
Przykład 6
Zobacz pliki sequence/sequence6.in oraz sequence/sequence6.ans w katalogu zawodnika.
Przykład spełnia ograniczenia testów od $16$ do $18$.
Ograniczenia
Niech $N$ oznacza sumę wartości $n$ we wszystkich zestawach danych w jednym teście. Dla wszystkich danych gwarantuje się:
- $1\le t\le20$;
- $1\le n\le5\,000$, $N\le4\times10^4$;
- dla każdego $1\le i\le n$ zachodzi $1\le A_i\le10^9$;
- dla każdego $1\le i\le n$ zachodzi $-10^9\le B_i\le10^9$;
- dla każdego $1\le i\le n$ zachodzi $1\le C_i\le10^9$.
| Numery testów | $n\le$ | $N\le$ | Szczególna własność |
|---|---|---|---|
| $1,2$ | $8$ | $10^2$ | Brak |
| $3,4$ | $200$ | $400$ | B |
| $5,6$ | $200$ | $400$ | Brak |
| $7$ | $500$ | $10^3$ | A |
| $8$–$10$ | $500$ | $10^3$ | B |
| $11,12$ | $500$ | $10^3$ | Brak |
| $13$ | $3\,500$ | $3\times10^4$ | A |
| $14,15$ | $3\,500$ | $3\times10^4$ | B |
| $16$–$18$ | $3\,500$ | $3\times10^4$ | Brak |
| $19,20$ | $5\,000$ | $4\times10^4$ | Brak |
Szczególna własność A: gwarantuje się, że $A_1=A_2=\cdots=A_n=1$.
Szczególna własność B: gwarantuje się, że dla każdego $1\le i\le n$ wartość $A_i$ jest losowana niezależnie i jednostajnie z przedziału $[1,10^9]$.
Podzadania
Dla każdego testu:
- Poprawne wyznaczenie $\max_{D\in T(A)}f(D)$ dla wszystkich zestawów danych daje $40\%$ punktów za ten test.
- Poprawne wyznaczenie reszty z dzielenia $\sum_{D\in T(A)}g(D)$ przez $1\,000\,000\,007$ dla wszystkich zestawów danych daje $60\%$ punktów za ten test.
Nawet jeśli odpowiadasz tylko na jedno z pytań, musisz zgodnie z formatem wyjścia wypisać dwie liczby całkowite, odpowiadające odpowiedziom na oba pytania.