A Vanessa é uma vendedora de arte, que tem N clientes aos quais vende pinturas artísticas. Cada cliente pode comprar pinturas a cores ou pinturas a preto e branco, mas não pinturas de ambos os tipos.
Cada cliente compra sempre pelo menos uma pintura, e o cliente i quer comprar um de máximo ai pinturas a cores ou um máximo de bi pinturas a preto e branco. Podes assumir que a Vanessa tem um número quase ilimitado de pinturas para venda, pelo que a quantidade de pinturas que cada cliente deseja nunca é um problema.
A Vanessa não gosta muito de vender pinturas a preto e branco, e por isso se não vender pinturas a cores a pelo menos C clientes, ela fica triste.
Os clientes estão sempre a mudar os seus requisitos, ou seja, a quantidade de pinturas que desejam comprar. Por causa disso, a Vanessa fica muitas vezes preocupada a pensar na seguinte pergunta: "De quantas maneiras diferentes posso vender as pinturas tal que pelo menos C clientes recebam pelo menos uma pintura colorida?". Ajuda a Vanessa, calculando este número depois de cada alteração de um cliente.
A primeira linha de input contém inteiros N e C, respetivamente o número total de clientes e o número mínimo de clientes que devem receber pinturas a cores.
A segunda linha contém N inteiros ai, as quantidades máximas de pinturas coloridas que cada cliente quer originalmente comprar.
A terceira linha contém N inteiros bi, as quantidades máximas de pinturas a preto e branco que cada cliente quer originalmente comprar.
A quarta linha contém um inteiro Q, o número de mudanças de requisitos. Cada uma das Q linhas seguintes contém três inteiros: P (o identificador do cliente que está a mudar os seus requisitos, e ap e bp, as novas quantidades máximas de pinturas coloridas e a preto e branco.
Q linhas, sendo que a késima linha contém o número de maneiras diferentes de realizar a venda depois de todas as alterações até k terem sido feitas. Este número deve vir módulo 10 007 (onde módulo representa o resto da divisão inteira).
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
1 ≤ N ≤ 100 000 | Número total de clientes | |
1 ≤ C ≤ 20 | Quantidade mínima de clientes que devem comprar pinturas a cores | |
1 ≤ Q ≤ 100 000 | Número de mudanças de requisitos | |
1 ≤ ai, bi ≤ 1 000 000 000 | Quantidades máximas de pinturas coloridas ou a preto e branco | |
1 ≤ P ≤ N | Identificador de um cliente que muda os seus requisitos |
Os casos de teste deste problema estão organizados em 2 grupos com restrições adicionais diferentes:
Grupo | Nº de Pontos | Restrições adicionais |
---|---|---|
1 | 30 | 1 ≤ N ≤ 1 000, 1 ≤ Q ≤ 1 000 |
2 | 70 | --- |
2 2 1 1 1 1 1 1 1 1
1
Depois do primeiro cliente mudar o seu pedido de (1,1) para (1,1), nada muda realmente, e o número de diferentes maneiras de vender é apenas uma. Esta maneira é vender ao primeiro cliente uma pintura colorida, e vender ao segundo cliente uma pintura colorida, pois todos os clientes têm de receber pelo menos uma pintura colorida (C=2)
2 2 1 2 2 3 2 1 2 2 2 2 2
4 4
Depois do primeiro cliente mudar o seu pedido de (1,2) para (2,2), ficamos com a=(2,2) e b=(2,3). Como C=2, ambos têm de receber pinturas coloridas, pelo que as 4 maneiras de vender são (1,1), (1,2), (2,1), (2,2). A segunda mudança não muda o valor de a2, pelo que continuamos com 4 maneiras.
4 2 1 2 3 4 1 2 3 4 1 4 1 1
66