CF175F Gnomes of Might and Magic

Vasya plays a popular game the Gnomes of Might and Magic. In this game Vasya manages the kingdom of gnomes, consisting of several castles, connected by bidirectional roads. The kingdom road network has a special form. The kingdom has $ m $ main castles $ a_{1},a_{2},...,a_{m} $ , which form the Good Path. This path consists of roads between the castles $ a_{i},a_{i+1} $ $ (1

The first line contains two integers $ n $ and $ m $ $ (3

For each query "?" print a single number on a single line — the number of very bad gnomes destroyed by the corresponding Mission of Death. Print the answers to queries in the chronological order.

In the example after the first four requests there is only one path from castle 1 to castle 2, which does not contain roads with very bad gnomes: 1  6  3  5  2. After a gnome stood on the road (2, 5), the next Mission of Death moves along path 1  2, and destroys the gnome, who was on the road (1, 2). The next Mission of Death follows the same path which is already free of gnomes. After yet another gnome stood on the road (1, 2), the next Mission of Death goes on the path 1  2, and kills the gnome.