画布染色

题目描述

小L有一个$n*n$的白色方格画布，为了让画布变得五颜六色，小L有四个操作

1 col pos ：将 1、2、……、pos列全部染上col色

2 col pos ：将pos、pos+1、……、n列染上col色

3 col pos ：将 1、2、……、pos行全部染上col色

4 col pos ：将pos、pos+1、……、n行染上col色

但是颜色具有消除效应，如果两次对一个格子染同一个颜色，那么相当于没有染色

颜色还有混合效应，也就是说一个格子可能有多个颜色

小L想知道，染完色之后各种颜色的面积

输入格式

第一行两个正整数 n，cnt，表示画布大小，颜色总数

第二行一个正整数m，表示操作数量

之后m行，每行三个正整数op，col，pos，意义如题目所言

按照排列组合，应该有$2^{cnt}$种不同的颜色（包括白色）

输出格式

$2^{cnt}$行，每行一个正整数，表示不同颜色的面积，按照从小到大排列

如果一个颜色不存在，则面积为0

样例

样例输入

3 3
7
1 1 1
2 1 3
3 1 1
4 1 3
3 2 1
2 2 3
4 3 2

样例输出

0
1
1
1
1
1
2
2

样例解释

图如下

2 12

13 3 123

3 13 23

没有的颜色是 1，右上角是白色

数据范围

第一到二个数据点，$n\le100,m\le100,cnt\le5$

第三到五个数据点，$n\le5000,m\le5000,cnt\le10$

第六到九个数据点，$n\le10^9,m\le10^5,cnt\le10$

第十个数据点，$n\le10^9,m\le10^5,cnt\le18$