有n盏灯，编号1~n。第1个人把所有灯打开，第2个人按下所有编号为2的倍数的灯（这些灯将被关掉），第3个人按下所有编号为3的倍数的开关（其中关掉的灯将被打开，开着的灯将被关闭），依此类推。一共有k个人。q次查询，每次查询一段区间开着的灯的数量。

第一行输入两个整数n,k(1<=k<=n<=100000)。第二行一个整数q(1<=q<=100000)。接下来q行，每行两个整数x,y(不保证x<y)，查询x~y之间的开着灯的个数。

q行，每行一个整数代表该段区间里面开着灯的个数。

GJ2022