Cặp số nguyên tố cùng nhau

Bob có một dãy $a$ gồm $n$ số nguyên dương $a_1,a_2,\dots ,a_n$.

Andy là bạn thân của Bob, cậu có một sở thích đặc biệt là mượn các con số của Bob về nhà để chơi. Trong $m$ ngày tới, mỗi ngày Andy sẽ tới mượn Bob một con số hoặc trả lại Bob một con số cậu đã mượn trước đó. Ban đầu Andy chưa mượn số nào.

Tuy nhiên, có một điều kiện để Andy có thể mượn được các con số của Bob. Sau mỗi ngày, Bob đố Andy trong các con số cậu đang mượn, có bao nhiêu cặp số nguyên tố cùng nhau. Nói cách khác, Andy cần tính số cặp chỉ số $i,j$ $(i\ne j)$ mà cậu đang mượn có $gcd(a_i,a_j)=1$. Mỗi cặp không phân biệt thứ tự, tức là $(i,j)$ và $(j,i)$ chỉ được tính một lần; hai chỉ số khác nhau có cùng giá trị $1$ vẫn tạo thành một cặp vì $gcd(1,1)=1$.

Bạn hãy giúp Andy trả lời các câu đố này nhé.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n,m$ là độ dài của dãy số của Bob và số ngày $(1\le n\le 5·{10}^5,1\le m\le 5·{10}^5)$.
• Dòng thứ hai chứa $n$ số nguyên dương $a_1,a_2,\dots ,a_n$ $(1\le a_i\le 5·{10}^5)$.
• $m$ dòng tiếp theo, mỗi dòng chứa một số nguyên $i$ $(1\le i\le n)$. Nếu trước đó Andy chưa mượn số nguyên $a_i$, Andy sẽ mượn số nguyên này ngay hôm đó, ngược lại cậu sẽ trả lại số nguyên này ngay hôm đó.

Dữ liệu ra

Gồm $m$ dòng, dòng thứ $i$ là đáp án cho câu đố trong ngày thứ $i$.

Ràng buộc

• $1\le n,m\le 5·{10}^5$.
• $1\le a_i\le 5·{10}^5$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $n,m\le 100$.
• Subtask 2 ($30\%$ số điểm): $n,m\le {10}^3$.
• Subtask 3 ($50\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ