# 不同顺子的牌组划分

预估时间限制：1.5 秒。内存限制：128 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

牌具工坊收到几批带有种类和数字的牌。整理员想把全部牌装成规定的组合，其中相同的顺子只能装一次。

(本故事由GPT-6重写)

## 形式化问题描述

牌有 $m$ 种，每种牌的数字可以是 $1,\ldots,n$ .开始时没有牌，随后收到 $k$ 批；第 $i$ 批包含 $a_i$ 张种类为 $b_i$ 、数字为 $c_i$ 的牌。同种同数字的牌只在数量上累加，不按批次区分。

判断能否把**所有牌恰好使用一次**，划分成以下两类组合：

- 顺子：同一种类、数字连续的三张或五张牌，每个数字恰好一张。任意两个顺子不能相同；即“种类、起始数字、长度”三者完全相同的顺子最多使用一个。
- 同牌组：种类和数字都相同的三张或四张牌。允许出现任意多个相同的同牌组。

两类组合都可以使用零组。不同种类或不同长度的顺子不视为相同。输出是否存在这样的划分。

## 输入格式

第一行三个整数 $n,m,k$ .接下来 $k$ 行，第 $i$ 行三个整数 $a_i,b_i,c_i$ .

## 输出格式

如果存在合法划分，输出一行 `1` ；否则输出一行 `0` .

## 样例

### 样例 1

### 输入

```text
5 1 5
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
```

### 输出

```text
1
```

### 样例 2

### 输入

```text
3 1 3
2 1 1
2 1 2
2 1 3
```

### 输出

```text
0
```

### 样例 3

### 输入

```text
1 2 3
1 1 1
2 1 1
4 2 1
```

### 输出

```text
1
```

## 样例解释

第一组使用一个长度为五的顺子。第二组若使用顺子，只能使用起点一、长度三的顺子一次，剩余三张牌无法组成合法组，因此无解。第三组把前两批的同牌累加成三张，再将另一种类的四张单独成组。

## 数据范围与保证

$1\le n,m,k\le5\times10^6$ , $1\le a_i\le10^9$ , $1\le b_i\le m$ , $1\le c_i\le n$ .

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |