[BJWC2018] Kreuzsummen

首先介绍一下Kakuro(カックロ) 这个游戏。 游戏规则为： • 方形空格中填入1 ~ 9 的整数。 • 被斜线分开的方格中，右上角的数字等于其右侧邻接之连续方格中数字之和，左下角的数字等于其下方邻接之连续方格中数字之和。 • 无论是横向还是纵向，连续方格中的数字不能重复。   左边为一个Kakuro 游戏，右边为这个游戏的唯一解。 我们称一开始给出的数字为线索，称需要填入数字的地方为空格。如果一个格子包含线索那么就不需要填入数字。我们约定所有的谜题都非空，即至少有一个空格需要被填入。 **注意：在以下题目中的游戏规则可能会有所不同，请认真阅读在每个 题目下的规则。**

游戏规则： • 方形空格中填入1 ~ k 的整数。 • 被斜线分开的方格中，右上角的数字等于其右侧邻接之连续方格中数字之和，左下角的数字等于其下方邻接之连续方格中数字之和。 • 无论是横向还是纵向，连续方格中的数字不能重复。 Apia 给了Rimbaud 一个Kakuro 谜题。心不灵手不巧的Rimbaud 发现自己总是做不出Kakuro。她怀疑原因是Apia 给的题目难度太高而不是自己太菜。所以她想评价一下这个题目的难度。 Rimbaud 认为一个Kakuro 谜题的难度为每个空格的候选数个数的和。我们来定义一下对于每个空格的候选数，这里的候选数为只考虑这个格子在初始谜题下对应的行和列线索和数字不能重复的条件下可以填的数字集合。 如果某连续4 个空格对应的线索为10，那么这四个数只可能是1 + 2 + 3 + 4，也就是这几个空格在这个线索的限制下候选数集合为{1, 2, 3, 4}。 更一般的，如果某连续c 个空格对应的线索为s，那么考虑所有数值1 ~ k 之间，不重复并且和为s 的c 元组，这几个空格在这个线索限制下的候选数集合为出现在这些c 元组中的所有数字。对于每个空格，它的候选数集合为行限制下的候选数和列限制下的候选数的交。  在这个谜题中，我们考虑第2 行第2 列的空格。这个空格的行线索为16，对应的候选数集合为{7, 9}。这个空格的列线索为23，对应的候选数{6, 8, 9}，所以这个空格的候选数集合为{9}。第2 行第3 列的空格的行线索对应的候选数集合为{7, 9}，列线索的I 应的候选数集合为{6, 7, 8, 9}，所以这个空格的候选数集合为{7, 9}。注意虽然我们可以通过先确定第2 行第2 列的数字，然后根据行线索推算出第2 行第3 列的数字，但是Rimbaud **只会考虑初始的线索**。 请帮助Rimbaud 求出这个谜题的难度即所有的空格的候选数个数的和。

第一行，四个正整数表示n, m, k, T 表示这个游戏的行，列，数值范围和总线索个数。 接下来T 行，每行五个正整数，$t, x, y_1, y_2, s(t \in \{0, 1\}, y_1 ≤ y_2)$。其中t 表示这个线索的种类，如果t = 0，那么表示这个线索为行线索，第x 行第y1 列到y2 列之间的数字和为s。如果t = 1，那么表示这个线索为行线索， 第x 列第y1 行到y2 行之间的数字和为s。数据中的行和列都从1 开始标号。 这个谜题的空格为所有线索对应的空格的并集。输入保证这个从格式上来说一定是个合法的Kakuro 谜题，即每一段连续的空格的左边或者上面的格子包含线索，并且每个空格出现了恰好两次。 **数据中可能出现某些位置的候选数集合为空或者无解的情况**。对于这种情况还是只需要按定义求出这个谜题的难度即可。

输出一个整数表示答案。

8 8 9 24
0 2 2 3 16
0 2 6 8 24
0 3 2 3 17
0 3 5 8 29
0 4 2 6 35
0 5 3 4 7
0 5 6 7 8
0 6 4 8 16
0 7 2 5 21
0 7 7 8 5
0 8 2 4 6
0 8 7 8 3
1 2 2 4 23
1 2 7 8 11
1 3 2 5 30
1 3 7 8 10
1 4 4 8 15
1 5 3 4 17
1 5 6 7 7
1 6 2 6 27
1 7 2 3 12
1 7 5 8 12
1 8 2 3 16
1 8 6 8 7

127

// 下面为这个样例的解释。 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 2 -1 -1 3 3 2 -1 2 2 -1 2 4 4 2 -1 3 4 1 2 5 -1 -1 -1 -1 1 5 -1 6 5 -1 -1 -1 -1 4 5 5 5 3 -1 8 8 5 6 -1 4 3 -1 2 3 3 -1 -1 2 2 对于10% 的数据，保证$n,m ≤ 3$。 对于30% 的数据，保证$n,m ≤ 50$。 对于50% 的数据，保证$n,m ≤ 500$。 对于另外20% 的数据，保证只有第一行第一列包含线索，剩下的地方全都是空格。 对于100% 的数据，保证$3 ≤ n, m, T ≤ 10^5, 1 ≤ k ≤ 10^5, s ≤ 10^{18}$。