406760: GYM102535 Q The Only Level TOO

You've proven your worth and capabilities as a spy when you passed The Only Level.

Your name isn't Mario but you fall down from a pipe.

You find an elephant in a room.

It speaks.

You are not sure if you are expecting an elephant in this scenario, but the elephant gives you no time to be confused as it tells you:

" The digital sum of an integer in base $$$b$$$ is the sum of its digits when it is written in base $$$b$$$. The digital root of an integer in base $$$b$$$ is the unique digit obtained by repeatedly computing the digital sum in base $$$b$$$ until only one digit remains.

Let $$$f_b(k)$$$ be the digital root of the integer $$$k$$$ in base $$$b$$$.

We say that the pair $$$(k,b)$$$ is cool if and only if $$$(f_b(0), f_b(k), f_b(2k), \ldots, f_b((b-1)k))$$$ is a permutation of $$$(0, 1, 2, \ldots, b-1)$$$.

Let $$$K$$$ and $$$B$$$ be two sets of integers. Find the number of distinct cool pairs $$$(k,b)$$$ such that $$$k \in K$$$ and $$$b \in B$$$. "

The first line of input contains two space-separated integers $$$|K|$$$ and $$$|B|$$$ denoting the sizes of the sets $$$K$$$ and $$$B$$$, respectively.

The second line of input contains $$$|K|$$$ space-separated integers denoting the elements of the set $$$K$$$.

The third line of input contains $$$|B|$$$ space-separated integers denoting the elements of the set $$$B$$$.

Constraints

$$$1\le |K|, |B| \le 3\cdot 10^5$$$

Every element of $$$K$$$ is a positive integer $$$\le 10^6$$$.

Every element of $$$B$$$ is a positive integer $$$\le 10^6$$$.

The elements of $$$K$$$ are distinct.

The elements of $$$B$$$ are distinct.

Output a single line containing a single integer denoting the answer.

4 3
6 9 11 24
8 16 10

6