Problema E - Pinturas

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.

O Problema

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.

Input

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.

Output

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).

Restrições

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 ---

Input de Exemplo 1

2 2
1 1
1 1
1
1 1 1

Output de Exemplo 1

1

Explicação do Exemplo 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)

Input de Exemplo 2

2 2
1 2
2 3
2
1 2 2
2 2 2

Output de Exemplo 2

4
4

Explicação do Exemplo 2

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.

Input de Exemplo 3

4 2
1 2 3 4
1 2 3 4
1
4 1 1

Output de Exemplo 3

66

1º Concurso de Treino das ONI'2020
(05/04 a 07/04 de 2020)