初级 DJ DIMAS 想要在 Byteland 连续举办 $d$ 场派对。众所周知，DJ DIMAS 的派对离不开灯光秀。举办派对的夜店里有 $n$ 个不同的灯泡。然而，在上一次狂欢之后，一些破坏者弄坏了所有的开关。现在 Dima 面临以下问题：他必须在某处找到新的开关。但由于 DJ DIMAS 还不富裕，购买开关是不可能的，所以他打算租用它们。由于 Byteland 还有其他 DJ，每个开关都有其可用的日期区间。

开关可以切换灯泡子集的状态。开关由一个包含 $n$ 个字符（0 和 1）的二进制字符串 $s$ 表示。如果第 $i$ 位是 1，则切换该开关后，第 $i$ 个灯的状态将变为相反（如果灯亮着，则熄灭；反之亦然）。

商店里有 $q$ 个开关。对于每个开关，给定其可租用的日期区间 $l$ 和 $r$。

DJ DIMAS 希望灯光秀尽可能多样化，因此在每场派对之前，他想知道在第 $i$ 天，利用当天所有可用的开关，他能组合出多少种不同的灯光开启状态。DJ DIMAS 没有太多时间准备新曲目，所以他请求你的帮助。

输入格式

第一行包含三个整数 $n, q$ 和 $d$，其中 $n$ 是灯泡的数量，$q$ 是开关的数量，$d$ 是举办派对的天数。

接下来的 $q$ 行包含有关开关的信息。每个开关的描述如下：

• $l \ r \ s$ — 开关可用的日期区间。$s$ 是一个包含 $n$ 个字符的 01 字符串（例如，如果 $n = 5$，$s$ 可以是 01101）。

$$1 \le n, q, d \le 500\,000$$ $$1 \le l \le r \le d$$

保证所有开关的字符串 $s$ 的总长度不超过 $500\,000$。

输出格式

输出 $d$ 个空格分隔的整数，其中第 $i$ 个整数（$1 \le i \le d$）表示在第 $i$ 天，利用当天可用的部分开关所能组合出的不同灯光开启状态的数量。值得注意的是，所有开关都可以不使用。

由于这些数字可能非常大，请输出它们对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

3 3 3
1 3 011
3 3 101
3 3 001

样例输出 1

2 2 8

样例输入 2

4 3 4
2 4 1010
2 4 0101
3 4 1101

样例输出 2

1 4 8 8

样例输入 3

5 2 2
1 2 01101
1 1 10101

样例输出 3

4 2