Ariana 非常富有。她有很多戒指，她会为朋友们购买钻石，而且一旦看到自己喜欢的物品，她就无法抗拒购买的冲动。

这就是为什么 Ariana 有许多不同颜色的衣服。形式化地说，有 $n$ 种类型的衣服或配饰，以及 $m$ 种颜色。每件衣服都可以由其类型和颜色来描述。

不出所料，Ariana 喜欢打扮得漂漂亮亮。如果一个包含 $n$ 件不同类型衣服的集合中至少包含 $k$ 种颜色的衣服，她就称其为“吸引人的集合”。每天开始时，她都会从拥有的衣服中挑选一个吸引人的集合。每天结束时，她会将这套衣服扔掉，因为她已经穿过了。

给定 Ariana 拥有的所有衣服，如果她以最优方式挑选吸引人的集合，求她不买新衣服最多能出门的天数（当然，并不是她买不起新衣服，这纯粹是出于好奇）。此外，确定每天穿什么以达到该天数。

输入格式

第一行包含三个整数 $n, m, c$ 和 $k$ ($1 \le n, m \le 100, 1 \le c \le 5000, 1 \le k \le \min(n, m)$)，分别表示衣服的类型数量、可能的颜色数量、Ariana 拥有的衣服总数以及吸引力阈值。接下来的 $c$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i \le n, 1 \le y_i \le m$)，表示一件类型为 $x_i$、颜色为 $y_i$ 的衣服。

输出格式

第一行输出唯一的整数 $d$：问题的答案。

在接下来的 $d$ 行中，第 $i$ 行输出 $n$ 个整数 $id_{i,1}, id_{i,2}, \dots, id_{i,n}$，描述第 $i$ 个吸引人的集合 ($1 \le id_{i,j} \le c$)。值 $id_{i,j}$ 必须是第 $i$ 个吸引人的集合中类型为 $j$ 的那件衣服的编号。注意，吸引人的集合中衣服的顺序很重要，因为必须满足 $x_{id_{i,j}} = j$。每个集合必须包含至少 $k$ 种不同颜色的衣服，且每件衣服不得使用超过一次。

如果有多种大小为 $d$ 的吸引人集合列表，输出其中任意一种即可。

样例

样例输入 1

3 3 10 2
3 1
3 3
3 2
2 3
2 2
2 2
3 3
2 1
1 3
1 3

样例输出 1

2
9 5 7
10 6 3

样例输入 2

3 4 12 3
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4

样例输出 2

4
3 6 9
4 7 10
1 8 11
2 5 12