题目描述

给定 n 个正整数：a1,a2,...,an，请计算一组乘积，记为 其中  的定义如下：

也就是说 ，是 a1到 an的连乘（除去 ai）。由于答案可能比较大，输出每个  模10000 的余数。

输入格式

第一行：单个正整数表示 n；
第二行：n 个正整数表示 a1,a2,...,an。

输出格式

共 n 行：第 i 行输出 。

数据范围

对于 30% 的数据，2≤n≤1000；

对于 60% 的数据，2≤n≤10000；

对于 100% 的数据，2≤n≤100000，1≤ai≤10000。

样例数据

输入:

4

1 3 4 6

输出:

72

24

18

12