题目描述

实验室给一批能量编号设置了两个校验规则。对于一个正整数 $x$，若 $x$ 的十进制各位数字之和能被 $k$ 整除，并且 $x$ 的二进制表示中 $1$ 的个数为偶数，则称 $x$ 为合格编号。给定整数 $L$、$R$ 和 $k$，请统计区间 $[L,R]$ 中合格编号的数量，并输出其中最小的合格编号。

输入格式

输入一行，包含三个整数 $L$、$R$、$k$。

输出格式

输出一行，包含两个整数 cnt 和 first。cnt 表示合格编号的数量；若存在合格编号，first 表示最小的合格编号，否则 first 输出 $-1$。

样例

10 20 3

3 12

样例解释

$12$ 的数字和为 $3$，二进制 1100 中有 $2$ 个 $1$；$15$ 的数字和为 $6$，二进制 1111 中有 $4$ 个 $1$；$18$ 的数字和为 $9$，二进制 10010 中有 $2$ 个 $1$。因此共有 $3$ 个合格编号，最小的是 $12$。

数据范围

$1 \le L \le R \le 100000$，$1 \le k \le 9$。

答案数量不超过 int 范围。