题目描述

给定 $n$ 个整数，请计算一组乘积，记为 $P_1,P_2,...,P_n$ ，其中 $P_i$的定义如下：

$P_i=\frac{a_1*a_2*...a_n}{a_i}$

也就是说 $P_i$ 是 $a_1$ 到 $a_n$ 的连乘再除去 $a_i$。由于答案可能比较大，输出每个 $P_i$ 模 $10000$ 的余数。

输入格式

第一行：单个整数表示 $n$ ；

第二行： $n$ 个整数表示 $a_1,a_2,...,a_n$ 。 。

输出格式

共 $n$ 行：第 $i$ 行输出 $P_i$ 模 $10000$ 的余数。

样例

输入样例1

4

1 3 4 6

输出样例1

72

24

18

12

提示

对于 $100\%$ 数据，$2\le n \le 10^6$,$2\le a_i \le 10^5$