题目描述

3030 年，Macsy 正在火星部署一批机器人。

第 $1$ 秒，他把机器人 $1$ 号运到了火星，机器人 $1$ 号可以制造其他的机器人。
第 $2$ 秒，机器人 $1$ 号造出了第一个机器人——机器人 $2$ 号。
第 $3$ 秒，机器人 $1$ 号造出了另一个机器人——机器人 $3$ 号。

之后每一秒，机器人 $1$ 号都可以造出一个新的机器人。第 $m$ 秒造出的机器人编号为 $m$。我们可以称它为机器人 $m$ 号，或者 $m$ 号机器人。

机器人造出来后，马上开始工作。$m$ 号机器人，每 $m$ 秒会休息一次。比如 $3$ 号机器人，会在第 $6$，$9$，$12$，$\ldots$ 秒休息，而其它时间都在工作。

机器人休息时，它的记忆将会被移植到当时出生的机器人的脑中。比如 $6$ 号机器人出生时，$2$，$3$ 号机器人正在休息，因此，$6$ 号机器人会收到第 $2$，$3$ 号机器人的记忆副本。我们称第 $2$，$3$ 号机器人是 $6$ 号机器人的老师。

如果两个机器人没有师徒关系，且没有共同的老师，则称这两个机器人的知识是互相独立的。注意：$1$ 号机器人与其他所有机器人的知识独立（因为只有 $1$ 号才会造机器人），它也不是任何机器人的老师。

一个机器人的独立数，是指所有编号比它小且与它知识互相独立的机器人的个数。比如 $1$ 号机器人的独立数为 $0$，$2$ 号机器人的独立数为 $1$（$1$ 号机器人与它知识互相独立），$6$ 号机器人的独立数为 $2$（$1$，$5$ 号机器人与它知识互相独立，$2$，$3$ 号机器人都是它的老师，而 $4$ 号机器人与它有共同的老师——$2$ 号机器人）。

新造出来的机器人有 $3$ 种不同的职业。对于编号为 $m$ 的机器人，如果能把 $m$ 分解成偶数个不同奇素数的积，则它是政客，例如编号 $15$；否则，如果 $m$ 本身就是奇素数或者能把 $m$ 分解成奇数个不同奇素数的积，则它是军人，例如编号 $3$，编号 $165$。其它编号的机器人都是学者，例如编号 $2$, 编号 $6$, 编号 $9$。

第 $m$ 秒诞生的机器人 $m$ 号，想知道它和它的老师中，所有政客的独立数之和，所有军人的独立数之和，以及所有学者的独立数之和。可机器人 $m$ 号忙于工作没时间计算，你能够帮助它吗？

为了方便你的计算，Macsy 已经帮你做了 $m$ 的素因子分解。为了输出方便，只要求输出总和除以 $10000$ 的余数。

输入格式

输入的第一行是一个正整数 $k$，$k$ 是 $m$ 的不同的素因子个数。

以下 $k$ 行，每行两个整数，$p_i$, $e_i$,表示 $m$ 的第 $i$ 个素因子和它的指数 $(i=1,2,\ldots,k)$。$p_1,p_2,\ldots,p_k$ 是不同的素数，$\prod_{i=1}^kp_i^{e_i}$。所有素因子按照从小到大排列，即 $p_1<p_2<\ldots<p_k$。

输出格式

输出包括三行。

• 第一行是机器人 $m$ 号和它的老师中，所有政客的独立数之和除以 $10000$ 的余数。
• 第二行是机器人 $m$ 号和它的老师中，所有军人的独立数之和除以 $10000$ 的余数。
• 第三行是机器人 $m$ 号和它的老师中，所有学者的独立数之和除以 $10000$ 的余数。

3
2 1
3 2
5 1

8
6
75

数据范围与提示

对于全部的数据，$1 \le k \le 1000$，$2 \le p_i < 10000$，$1 \le e_i \le 10^6$。

你在一个测试点的得分与你正确解决的问题数 $x$ 有关。

请注意：对每一行，即使不会解决该问题，也请在该行输出一个数字，否则 checker 将无法正确评分。