F. Bessie at the Bank
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bessie recently got a job working at Cowpital One, the largest cow-run bank in the country! She was having a perfectly fine day not worrying about algorithmic problems until one of her clients keeps making mistakes when giving her a security code that consists of $$$N$$$ numbers $$$a_1, a_2, \ldots, a_N$$$, which really annoys her.

The client will make $$$Q$$$ corrections to her previous codes, one at each time $$$t = 1, 2, \ldots, Q$$$ (time $$$0$$$ is the original code). The $$$i$$$-th correction (at time $$$i$$$) consists of:

  1. Referring to a previous time $$$t_i$$$ ($$$0 \le t_i \lt i$$$).
  2. Updating the code at time $$$t_i$$$ by replacing the $$$u_i$$$-th number with a new number $$$x_i$$$.

In other words, the code at time $$$i$$$ is equal to the code at time $$$t_i$$$ ($$$0 \le t_i \lt i$$$) with up to one value changed.

Since Bessie is so annoyed, she tries to calm herself down by thinking of her $$$D$$$ favorite numbers $$$d_1, d_2, \ldots, d_D$$$. It is guaranteed that all $$$d_i$$$ are distinct. After each correction (and for the original code), Bessie wants to compute the sum of all favorite numbers $$$d_k$$$ that divide every number $$$a_j$$$ in the current security code.

Help Bessie calm herself down!

Input

The first line contains three integers $$$N$$$, $$$Q$$$, and $$$D$$$ ($$$1 \le N \le 2 \cdot 10^5$$$, $$$1 \le Q \le 2 \cdot 10^5$$$, $$$1 \le D \le 30$$$).

The second line contains $$$D$$$ distinct integers $$$d_1, d_2, \ldots, d_D$$$ ($$$2 \le d_i \le 10^{18}$$$) — Bessie's favorite numbers.

The third line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ ($$$1 \le a_j \le 10^{18}$$$) — the initial security code.

The next $$$Q$$$ lines each contain three integers $$$t_i$$$, $$$u_i$$$, and $$$x_i$$$ ($$$0 \le t_i \lt i$$$, $$$1 \le u_i \le N$$$, $$$1 \le x_i \le 10^{18}$$$) — the time to base the correction on, the index to update, and the new value.

Output

Print $$$Q + 1$$$ integers, one per line. The $$$i$$$-th integer (0-indexed) should be the sum of all favorite numbers that divide every number in the security code at time $$$i$$$.

Example
Input
3 3 3
2 3 5
10 15 20
0 2 30
1 1 6
1 1 7
Output
5
7
2
0
Note

Bessie's favorite numbers are $$$2$$$, $$$3$$$, and $$$5$$$.

  • Time 0: The original code is $$$[10, 15, 20]$$$. Only $$$5$$$ divides all numbers, so the sum $$$= 5$$$.
  • Time 1: Based on time $$$0$$$, the second number becomes $$$30$$$, giving $$$[10, 30, 20]$$$. Both $$$5$$$ and $$$2$$$ divide all numbers, so the sum $$$= 5 + 2 = 7$$$.
  • Time 2: Based on time $$$1$$$, the first number becomes $$$6$$$, giving $$$[6, 30, 20]$$$. Only $$$2$$$ divides all numbers, so the sum $$$= 2$$$.
  • Time 3: Based on time $$$1$$$, the first number becomes $$$7$$$, giving $$$[7, 30, 20]$$$. None of Bessie's favorite numbers divide every number, so the sum $$$= 0$$$.