有N个人，编号为1至N，他们相互之间拜师学艺。

某个时刻，如果甲向乙拜师，一般情况下乙就将甲收为徒弟。这时乙会将甲视为大徒弟，而所有甲的徒弟（如果有的话）便成为乙的小徒弟。

但是，每个人都不想收太多的大徒弟。如果乙当前大徒弟数量超过他的期望值，他便会拒绝甲，而让甲拜自己的某一位大徒弟为师。甲总是想选好的师傅，而如果一个人的所有徒弟数量很多，往往说明他水平比较高，所以甲会选乙的徒弟中，拥有最多徒弟的人。如果有不止一个人徒弟最多，甲会选择最早向乙拜师的那位。于是接下来，就是新的一次拜师过程，甲向乙的某位徒弟拜师。甲直到拜师成功才会停止。

每个人每一时刻最多只会有一个师傅。有师傅的人若再向其他人拜师，就会先断绝与当前师傅的师徒关系。若甲不认乙为师，乙也就不认甲为大徒弟，同时甲和他的徒弟们也因此与甲的师傅脱离关系（当然包括师傅的师傅，师傅的师傅的师傅……）。

两个人之间的师徒关系可能是变化的。所以若甲向乙多次拜师，则甲向乙拜师的时间将以最后一次拜师的时间算。

一开始，每个人都没有师傅，也没有徒弟。我们事先告诉你每个人愿意收的最多大徒弟数量，达到了这个数量，他就不再收大徒弟，除非又有某个大徒弟与他断绝了关系。接下来每一时刻，就有人相互拜师，而所有拜师都会按照上面的规则进行。此外，一个人也不会向自己当前的任何一位徒弟拜师。
请你统计，所有拜师过程结束后，每个人有多少大徒弟，小徒弟。

第一行给出两个整数N和M（5<=N<=10000，0<=M<=10000），其中N表示总人数，M表示有多少组拜师的人。

第二行，包含N个正整数，依次表示每个人愿意收的最多大徒弟的数量。

接下来M行，每行两个整数A和B，按时间顺序依次表示一对拜师的人。总是A向B拜师。

输出包括N行，每行有两个整数，之间用一个空格隔开。第i行的两个数分别表示，在所有拜师结束后，编号为i的人拥有的大徒弟数量和小徒弟数量。