题目描述

给定 $n$ 个整数 $a_1,a_2,\cdots,a_n$，请计算一组乘积，记为 ${P}_1,{P}_2,\cdots,{P}_n$，其中 ${{P}_i}$ 的定义如下：

$${{P}_i}=\frac{a_1\cdot a_2\cdot a_3\cdots a_n}{a_i}$$

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

输入格式

• 第一行：单个整数表示 $n$；
• 第二行：$n$ 个整数表示 $a_1,a_2,\cdots,a_n$。

输出格式

共 $n$ 行：第 $i$ 行输出 ${P}_i$ 模 ${10000}$ 的余数。

数据范围

• 对于 $30\%$ 的数据，$2\leq n\leq 1000$；
• 对于 $60\%$ 的数据，$2\leq n\leq 10000$；
• 对于 $100\%$ 的数据，$2\leq n\leq 100000$，$1\leq a_i \leq 10000$。

样例数据

输入:

4
1 3 4 6

输出:

72
24
18
12