← 返回题目列表

Codeforces · 769/D

D. k-有趣的整数对

中文机器翻译题面 查看原题

Vasya 具有由 n 个整数组成的序列。 Vasya 认为整数对 x 和 y k 是有趣的,如果它们的二进制表示在 k 位上彼此完全不同。例如,如果 k = 2,则整数对 x = 5 和 y = 3 是 k 有趣的,因为它们的二进制表示形式 x=101 和 y=011 恰好有两位不同。

Vasya 想知道他的序列中有多少对索引 (i, j),使得 i < j 并且整数对 ai 和 aj 是 k-感兴趣的。你的任务是帮助 Vasya 并确定这个数字。

输入

第一行包含两个整数 n 和 k (2 ≤ n ≤ 105, 0 ≤ k ≤ 14) — Vasya 序列中整数的数量以及 k 感兴趣对中整数应该不同的位数。

第二行包含 Vasya 拥有的序列 a1, a2, ..., an (0 ≤ ai ≤ 104)。

输出

打印 (i, j) 对的数量,使得 i < j 并且整数对 ai 和 aj 是 k 感兴趣的。

示例

输入 #1

4 1
0 3 2 1

输出 #1

4

输入 #2

6 0
200 100 100 100 200 200

输出 #2

6

注意

在第一个测试中,有 4 k 个感兴趣的对:

- (1, 3),
- (1, 4),
- (2, 3),
- (2, 4).

在第二个测试中,k = 0。因此,任何 k 感兴趣的对中的整数都应该等于它们自己。因此,对于第二个测试,有 6 k 个感兴趣的对:

- (1, 5),
- (1, 6),
- (2, 3),
- (2, 4),
- (3, 4),
- (5, 6).