筱玛是一个热爱线段树的好筱玛。 筱玛的爷爷马爷在游戏中被筱玛吊打了，于是他恼羞成怒，决定给筱玛出这样一道数据结构题： 给定一个长度为的数组，刚开始每一项的值均为。 支持以下两种操作，操作共次： ：将的每一项的值加上。 ：执行操作编号在内的所有操作各一次，保证小于当前操作的编号。 次操作结束后，你要告诉马爷数组变成什么样子了。 由于答案可能会很大，你只需要输出数组中的每个数在模意义下的值。

输入描述:

第一行两个数，分别表示数组长度及操作次数。接下来行，每行三个数，表示一次操作。

输出描述:

输出一行共个数，表示次操作结束后，的值。

备注:

对于100%的数据，。