São dadas duas sequências de inteiros de comprimento $n$, $B=[b_1,\ldots,b_n]$ e $C=[c_1,\ldots,c_n]$. Para uma sequência de inteiros não negativos $D=[d_1,\ldots,d_n]$ de comprimento $n$, seja $S(D)$ o conjunto dos índices $i$ tais que $d_i=0$. Definimos $f(D)=\sum_{i\in S(D)}b_i$ e $g(D)=\prod_{i\in S(D)}c_i$. Em particular, se $S(D)$ for vazio, $f(D)=0$ e $g(D)=1$.
Xiao L tem uma sequência de inteiros positivos $A=[a_1,\ldots,a_n]$. Ele pode modificar $A$ da seguinte forma:
- Escolhe dois índices adjacentes $i,j$ de $A$ (isto é, $1\le i,j\le n$ e $|i-j|=1$). Se $a_i\le a_j$, substitui $a_j$ por $a_j-a_i$ e, simultaneamente, $a_i$ por $0$.
Xiao L pode realizar um número arbitrário de modificações, inclusive nenhuma. Entre todas as sequências $D$ que podem ser obtidas de $A$ por essas operações, ele quer encontrar o maior valor de $f(D)$ e a soma dos valores de $g(D)$. Ajude-o a calcular esses dois valores. Formalmente, seja $T(A)$ o conjunto de todas as sequências alcançáveis a partir de $A$ pelas operações descritas. Calcule $\max_{D\in T(A)}f(D)$ e $\sum_{D\in T(A)}g(D)$. Como a soma pode ser grande, calcule apenas seu resultado módulo $1\,000\,000\,007$.
Entrada
Leia os dados do arquivo sequence.in.
Este problema contém vários conjuntos de dados de teste.
A primeira linha contém dois inteiros não negativos $c,t$, indicando o número do caso de teste e o número de conjuntos de dados, respectivamente. $c=0$ indica um exemplo.
Em seguida são fornecidos, em ordem, os conjuntos de dados. Para cada conjunto:
A primeira linha contém um inteiro positivo $n$, o comprimento das sequências.
A segunda linha contém $n$ inteiros positivos $a_1,\ldots,a_n$, a sequência $A$.
A terceira linha contém $n$ inteiros $b_1,\ldots,b_n$, a sequência $B$.
A quarta linha contém $n$ inteiros positivos $c_1,\ldots,c_n$, a sequência $C$.
Saída
Escreva a saída no arquivo sequence.out.
Para cada conjunto de dados, imprima apenas uma linha com dois inteiros: $\max_{D\in T(A)}f(D)$ e o resultado de $\sum_{D\in T(A)}g(D)$ módulo $1\,000\,000\,007$, respectivamente. Atenção: $\max_{D\in T(A)}f(D)$ não deve ser reduzido módulo $1\,000\,000\,007$.
Este problema tem duas perguntas. Responder corretamente a qualquer uma delas permite obter pontuação parcial. Consulte a seção Pontuação para as regras específicas.
Exemplos
Entrada 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
Saída 1
15 10 1 18 37 48
Nota
Este exemplo contém três conjuntos de dados.
Para o primeiro conjunto, podem ser obtidas as seguintes $4$ sequências:
- $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$.
Portanto, $\max_{D\in T(A)}f(D)=\max\{0,3,15,9\}=15$ e $\sum_{D\in T(A)}g(D)=1+1+6+2=10$.
Exemplo 2
Veja sequence/sequence2.in e sequence/sequence2.ans no diretório dos competidores.
Esse exemplo satisfaz as restrições dos casos de teste $3,4$.
Exemplo 3
Veja sequence/sequence3.in e sequence/sequence3.ans no diretório dos competidores.
Esse exemplo satisfaz as restrições dos casos de teste $5,6$.
Exemplo 4
Veja sequence/sequence4.in e sequence/sequence4.ans no diretório dos competidores.
Esse exemplo satisfaz as restrições do caso de teste $7$.
Exemplo 5
Veja sequence/sequence5.in e sequence/sequence5.ans no diretório dos competidores.
Esse exemplo satisfaz as restrições dos casos de teste $11,12$.
Exemplo 6
Veja sequence/sequence6.in e sequence/sequence6.ans no diretório dos competidores.
Esse exemplo satisfaz as restrições dos casos de teste $16\sim18$.
Restrições
Seja $N$ a soma dos valores de $n$ entre todos os conjuntos de dados de um caso de teste. Para todos os dados, garante-se:
- $1\le t\le20$;
- $1\le n\le5000$, $N\le4\times10^4$;
- Para todo $1\le i\le n$, $1\le A_i\le10^9$;
- Para todo $1\le i\le n$, $-10^9\le B_i\le10^9$;
- Para todo $1\le i\le n$, $1\le C_i\le10^9$.
| Casos de teste | $n\le$ | $N\le$ | Propriedade especial |
|---|---|---|---|
| $1,2$ | $8$ | $10^2$ | Nenhuma |
| $3,4$ | $200$ | $400$ | B |
| $5,6$ | $200$ | $400$ | Nenhuma |
| $7$ | $500$ | $10^3$ | A |
| $8\sim10$ | $500$ | $10^3$ | B |
| $11,12$ | $500$ | $10^3$ | Nenhuma |
| $13$ | $3500$ | $3\times10^4$ | A |
| $14,15$ | $3500$ | $3\times10^4$ | B |
| $16\sim18$ | $3500$ | $3\times10^4$ | Nenhuma |
| $19,20$ | $5000$ | $4\times10^4$ | Nenhuma |
Propriedade especial A: $A_1=A_2=\cdots=A_n=1$.
Propriedade especial B: para todo $1\le i\le n$, $A_i$ é gerado independente e uniformemente ao acaso em $[1,10^9]$.
Pontuação
Para cada caso de teste:
- Responder corretamente a $\max_{D\in T(A)}f(D)$ para todos os conjuntos de dados concede 40% dos pontos do caso;
- Responder corretamente a $\sum_{D\in T(A)}g(D)$ módulo $1\,000\,000\,007$ para todos os conjuntos de dados concede 60% dos pontos do caso.
Atenção: mesmo que você responda apenas uma das perguntas, deve imprimir dois inteiros conforme o formato de saída, correspondentes às respostas das duas perguntas.