CF769D.k-Interesting Pairs Of Integers

Vasya has the sequence consisting of n integers. Vasya consider the pair of integers x and y k-interesting, if their binary representation differs from each other exactly in k bits. For example, if k = 2, the pair of integers x = 5 and y = 3 is k-interesting, because their binary representation x=101 and y=011 differs exactly in two bits.

Vasya wants to know how many pairs of indexes (i, j) are in his sequence so that i < j and the pair of integers a__i and a__j is k-interesting. Your task is to help Vasya and determine this number.

瓦西娅有一个由 $n$ 个整数组成的序列。瓦西娅称一对整数 $x$ 和 $y$ 是 $k$-有趣的，当且仅当它们的二进制表示恰好在 $k$ 个位上不同。例如，若 $k = 2$，则整数对 $x = 5$ 和 $y = 3$ 是 $k$-有趣的，因为它们的二进制表示 $x = 101$ 和 $y = 011$ 恰好在两个位上不同。

瓦西娅想知道：在他的序列中，有多少对下标 $(i, j)$ 满足 $i < j$，且整数 $a_i$ 和 $a_j$ 构成一对 $k$-有趣的数？你的任务是帮助瓦西娅求出这个数目。

The first line contains two integers n and k (2 ≤ n ≤ 105, 0 ≤ k ≤ 14) — the number of integers in Vasya's sequence and the number of bits in which integers in k-interesting pair should differ.

The second line contains the sequence _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ 104), which Vasya has.

第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 10^5$，$0 \leq k \leq 14$）——分别表示瓦西娅序列中整数的个数，以及“$k$-有趣”数对中两整数应当不同的二进制位数。

第二行包含序列 $a_1,\ a_2,\ \dots,\ a_n$（$0 \leq a_i \leq 10^4$），即瓦西娅所拥有的序列。

Print the number of pairs (i, j) so that i < j and the pair of integers a__i and a__j is k-interesting.

输出满足 $i < j$ 且整数对 $a_i$ 和 $a_j$ 是 $k$-有趣的有序对 $(i, j)$ 的个数。

In the first test there are 4 k-interesting pairs:

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

In the second test k = 0. Consequently, integers in any k-interesting pair should be equal to themselves. Thus, for the second test there are 6 k-interesting pairs:

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

在第一个测试中，有 4 个 $k$-interesting 数对：

• $(1, 3)$,
• $(1, 4)$,
• $(2, 3)$,
• $(2, 4)$。

在第二个测试中，$k = 0$。因此，任意 $k$-interesting 数对中的两个整数必须彼此相等（即该数对为形如 $(x, x)$ 的数对）。于是，第二个测试中有 6 个 $k$-interesting 数对：

• $(1, 5)$,
• $(1, 6)$,
• $(2, 3)$,
• $(2, 4)$,
• $(3, 4)$,
• $(5, 6)$。