Республиканская олимпиада по информатике 2019 года за 11 класс | Казахстанские олимпиады

Задача B. Array

Ограничение по времени Ограничение по памяти
2 секунды 256 мегабайт

Дан массив aa длины kk. Так же, имеются nn массивов длины kk. Массив xx называется хорошим, если существует перестановка pp длины kk, такая что для каждого ii (1<=i<=k)(1 <= i <= k) выполняется xpi0(modai)x_{p_i} \equiv 0 \pmod{a_i}.

Вам необходимо посчитать количество пар (l,r)(l, r) (1<=l<=r<=n)(1 <= l <= r <= n), таких что количество хороших массивов в отрезке больше чем нехороших.

Формат входного файла

В первой строке входных данных даются числа nn и kk (1<=n<=105,1<=k<=20)(1 <= n <= 10^5, 1 <= k <= 20).

Во второй строке входных данных даётся массив aa длины kk (1<=ai<=109)(1 <= a_i <= 10^9).

В следующих nn строк даются массивы длины kk, где в ii-ой содержится массив bib_i (1<=bij<=109,(1 <= b_{ij} <= 10^9, где 1<=i<=k)1 <= i <= k).

Формат выходного файла

В единственной строке выходных данных выведите одно число - ответ на задачу.

Примеры

Вход

3 1
2
1
2
2

Выход

4