[JSOI2019] 精准预测

题目背景

JYY 和他的火星探险队再次登录火星小镇,并且打算把机器学习的知识传授给火星人,从而提高火星人的生活效率。但智力有限的火星人纷纷表示不相信计算机科学。为了让火星人彻底信服,JYY 的探险队找到了他们之前关于火星详细的数据记录,并且训练了一个预测模型,这个模型能准确地预测出火星人在未来的生死情况。

题目描述

目前,火星小镇上有$n$个居民(编号$1,2,……,n$)。机器学习算法预测出这些居民在接下来$T$个时刻(编号$1,2,……,T$)的生死情况,每条预测都是如下两种形式之一: - 难兄难弟$0$ $t$ $x$ $y$:在$t$时刻,如果$x$是死亡状态,那么在$t+1$时刻,$y$是死亡状态。(注意,当$x$在$t$时刻是生存状态时,该预测也被认为是正确的); - 死神来了$1$ $t$ $x$ $y$:在$t$时刻,如果$x$是生存状态,那么在$t$时刻,$y$是死亡状态。(注意,当$x$在$t$时刻是死亡状态时,该预测也被认为是正确的)。 注意本题是对某个时刻进行生死状态的预测,如果某个人在$t$时刻是生存状态,在$t+1$时刻是死亡状态,你可以认为是在$t$到$t+1$这段时间内发生了某个事件导致其死亡。 虽然 JYY 对自己从大数据中统计得到的模型非常自信,但火星人看到这些预测吓了一跳,表示实在难以接受这种设定,更是认为计算机科学是可怕的邪教,打破了他们平静的生活。为了安抚火星人的情绪, JYY 打算从这些预测结果中推导出一些火星人更容易接受的事实,从而安抚火星人的情绪。 具体来说,JYY 首先假设对火星人生死的预测全部正确,在此基础上,JYY 希望为小镇上的每个居民$k$分别计算有多少个火星人有可能和他一起活到第$T+1$时刻,换言之,JYY 希望为每个火星人$k$计算 $$\sum_{1 \leq i \leq n,i \neq k} \operatorname{Live}(k,i)$$ 其中 $\operatorname{Live}(i,j)=1$ 表示编号为$i$和$j$的火星人有可能同时在第 $T+1$ 时刻处于生还状态,否则$\operatorname{Live}(i,j)=0$。 注意火星人是不能够复活的。一个火星人可能在时刻$1$就处于死亡状态,也有可能有预测未覆盖的死亡情况发生(火星人在任何时候都可能死亡,但任意时刻观察到火星人的状态要么活着,要么死亡)。最后,注意到$\operatorname{Live}$是为每一对火星人分别独立计算的,因此$\operatorname{Live}(x,y)=1,\operatorname{Live}(y,z)=1$并不意味着$\operatorname{Live}(x,z)=1$。

输入输出格式

输入格式


输入第一行包含三个整数$T,n,m$。 接下来有$m$行,每行表示一条预言,每条预言第一个整数$c$表示预言的类型: - $c=0$:接下来读入$t,x,y$; - $c=1$:接下来读入$t,x,y$。

输出格式


输出$n$个数表示答案,用空格分割。

输入输出样例

输入样例 #1

3 3 2
0 2 1 3
1 1 2 3

输出样例 #1

2 1 1

说明

![](https://cdn.luogu.com.cn/upload/pic/57734.png)