Luzes na rotatória

Time limit: 3000 msMemory limit: 256 MB

Há $n$ luminárias em uma rotatória, numeradas de $1$ a $n$ no sentido horário. A luminária $i$ pode ser ajustada para uma intensidade inteira $x_i\in\{0,1,2\}$ , com custo $c_i x_i$ .

Para cada $i$ , um relatório exige que a soma das intensidades das $k$ luminárias consecutivas que começam em $i$ seja exatamente $a_i$ . A numeração é circular: depois da luminária $n$ vem a luminária .

Encontre o menor custo total de uma configuração que satisfaça todos os relatórios e o número de configurações que atingem esse custo, módulo $998244353$ . Duas configurações são diferentes se alguma luminária tem intensidades diferentes; rotações não são identificadas. Se os relatórios forem incompatíveis, informe isso.

Input

A primeira linha contém $n$ e $k$ ( $1\le k\le n\le 200000$ ). A segunda linha contém $n$ inteiros (). A terceira linha contém inteiros ().

Output

Imprima dois inteiros: o custo mínimo e o número de configurações ótimas módulo $998244353$ . Se não existir configuração válida, imprima -1 0.

Samples

Sample 1

Input

4 2
1 1 1 1
3 1 1 3

Output

4 2

As configurações $(1,0,1,0)$ e $(0,1,0,1)$ têm custo 4. Os relatórios não permitem intensidade 2 nesta instância.

Sample 2

Input

3 2
0 0 1
1 2 3

Output

-1 0

Os dois primeiros relatórios forçam todas as intensidades a zero, contrariando o último.

Sample 3

Input

3 3
2 2 2
4 1 1

Output

2 3