CF167D Wizards and Roads

In some country live wizards. They love to build cities and roads. The country used to have $ k $ cities, the $ j $ -th city ( $ 1

The first line contains two space-separated integers $ n $ , $ k $ ( $ 1

For any pair of numbers $ L_{i} $ , $ R_{i} $ print the answer to the problem on a single line. Print the answers for the pairs in the order, in which the pairs are given in the input data.

In the first sample the roads connect the cities in a chain in the order of increasing of $ x $ . In the second sample the remaining 5 cities will be located at points $ (5, 11); (20, 263098); (65, 292514823); (200, 76958738); (605, 622120197) $ .