题目描述

在开发过程中我们经常需要使用到id，但是在想要生成一些全局唯一且保持自增的id是十分困难的。此时雪花算法就应运而生，他使用一个 64 bit 的 long 型的数字作为全局唯一 id。在分布式系统中的应用十分广泛，且ID 引入了时间戳，基本上保持自增。

给大家举个例子吧，比如上面那个 64 bit 的 long 型数字：


第一个部分，是 1 个 bit：0，这个是无意义的，因为这在转换为long型数字时代表正负而我们想生成id全是正数。


第二个部分是 41位二进制数：表示的是生成id时的时间戳。


第三个部分是 5 位二进制数：表示的是机房 id，10001。


第四个部分是 5 位二进制数：表示的是机器 id，1 1001。


第五个部分是 12 位二进制数：表示的序号。可以在一毫秒中同时生成第0000

00000001到1111 11111111的序号，同一时间生成的id第一个为0000 00000001，第二个为0000 00000002每次在前一个数的基础上加一。

我们现在有N（1

每个机房中有M（1

现在有T(1

我们会分别提供生成的机房id,机器id和生成的时间戳


请将生成的id从小到大排列

输入格式

第一行一组N（1

第二行一个T(1

之后T行每行一组 x(1

输出格式

从小到大输出生成的id，每个id一行

2 2
3
1 1 10000
2 1 20000
1 2 30000

41943175169
83886346241
125829259265

提示

第一个数据根据规则生成的二进制数为

0000000000000000000000000000100111000100000000100001000000000001


转换为数字41943175169


第二个数据根据规则生成的二进制数为


0000000000000000000000000001001110001000000001000001000000000001


转换为数字83886346241


第三个数据根据规则生成的二进制数为


0000000000000000000000000001110101001100000000100010000000000001


转换为数字125829259265