1#include <iostream>
2#include <vector>
3#include <cstring>
4#include <set>
5#include <algorithm>
6#include <cstdio>
7
8using namespace std;
9const int N=1E4+7;
10int n,k,Q;
11int siz;
12int pos[N];
13int sum[N];
14int dis[N];
15bool vis[N];
16vector < pair<int,int> > edge[N];
17
18struct node
19{
20 int l,r;
21 int id;
22
23 bool operator < (node b)const
24 {
25 if (pos[l]==pos[b.l]) return r<b.r;
26 return pos[l]<pos[b.l];
27 }
28
29
30}q[N];
31
32
33void dfs( int u,int val)
34{
35 vis[u] = true;
36 dis[u+1] = val;
37
38 int Siz = edge[u].size();
39 for ( int i = 0 ; i < Siz ; i ++)
40 {
41 int v = edge[u][i].first;
42
43 if (!vis[v])
44 {
45 dfs(v,val+edge[u][i].second);
46 }
47 }
48}
49int main()
50{
51
52 freopen("in.txt","r",stdin);
53 siz = 100;
54 for ( int i = 0 ; i < 10000 ; i++) pos[i] = i/siz;
55 while (scanf("%d %d %d",&n,&k,&Q)!=EOF)
56 {
57 memset(vis,false,sizeof(vis));
58 memset(dis,0,sizeof(dis));
59 memset(sum,0,sizeof(sum));
60 for ( int i = 1 ;i < n ; i++)
61 {
62 int u = i;
63 int v = i/k;
64 edge[u].push_back(make_pair(v,i));
65 edge[v].push_back(make_pair(u,i));
66 }
67
68 for ( int i = 1 ;i <= Q ; i++)
69 {
70 scanf("%d %d",&q[i].l,&q[i].r);
71 q[i].id = i;
72 }
73
74 sort(q+1,q+Q+1);
75
76 dfs(0,0);
77 for ( int i = 1 ; i <= n ; i++) sum[i] = sum[i-1]+dis[i];
78 }
79}