{"raw_statement":[{"iden":"statement","content":"You've proven your worth and capabilities as a spy when you passed The Only Level.\n\nYour name isn't Mario but you fall down from a pipe.\n\nYou find an elephant in a room.\n\nIt speaks.\n\nYou 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:\n\n\" 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. \n\nLet $f_b (k)$ be the digital root of the integer $k$ in base $b$.\n\nWe say that the pair $(k, b)$ is *cool* if and only if $(f_b (0), f_b (k), f_b (2 k), \\\\dots, f_b ((b -1) k))$ is a permutation of $(0, 1, 2, \\\\dots, b -1)$. \n\nLet $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$. \"\n\nThe first line of input contains two space-separated integers $| K |$ and $| B |$ denoting the sizes of the sets $K$ and $B$, respectively. \n\nThe second line of input contains $| K |$ space-separated integers denoting the elements of the set $K$. \n\nThe third line of input contains $| B |$ space-separated integers denoting the elements of the set $B$. \n\n*Constraints*\n\n$1 <= | K |, | B | <= 3 dot.op 10^5$\n\nEvery element of $K$ is a positive integer $<= 10^6$.\n\nEvery element of $B$ is a positive integer $<= 10^6$.\n\nThe elements of $K$ are distinct.\n\nThe elements of $B$ are distinct.\n\nOutput a single line containing a single integer denoting the answer. \n\n"},{"iden":"input","content":"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 <= | K |, | B | <= 3 dot.op 10^5$Every element of $K$ is a positive integer $<= 10^6$.Every element of $B$ is a positive integer $<= 10^6$.The elements of $K$ are distinct.The elements of $B$ are distinct."},{"iden":"output","content":"Output a single line containing a single integer denoting the answer. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ f_b(k) $ denote the digital root of $ k $ in base $ b $, defined as the repeated sum of digits in base $ b $ until a single digit is obtained.  \n\n**Given**  \n- Finite sets $ K \\subset \\mathbb{Z}^+ $, $ B \\subset \\mathbb{Z}^+ $, with $ |K|, |B| \\leq 3 \\cdot 10^5 $.  \n- For each $ k \\in K $, $ k \\leq 10^6 $.  \n- For each $ b \\in B $, $ b \\leq 10^6 $.  \n\n**Constraint**  \nFor a pair $ (k, b) $ to be *cool*, the sequence  \n$$\n(f_b(0), f_b(k), f_b(2k), \\dots, f_b((b-1)k))\n$$  \nmust be a permutation of $ \\{0, 1, 2, \\dots, b-1\\} $.  \n\n**Objective**  \nCompute the number of distinct cool pairs $ (k, b) \\in K \\times B $.","simple_statement":"Count how many pairs (k, b) are cool, where k is from set K, b is from set B, and (f_b(0), f_b(k), f_b(2k), ..., f_b((b-1)k)) is a permutation of (0, 1, 2, ..., b-1).","has_page_source":false}