B"Squirrel Liss loves nuts. Liss asks you to plant some nut trees. There are n positions (numbered 1 to n from west to east) to plant a tree along a street. Trees grow one meter per month. At the beginning of each month you should process one query. The query is one of the following types: After processing each query, you should print the length of the longest increasing subsequence. A subset of existent trees is called an increasing subsequence if the height of the trees in the set is strictly increasing from west to east (for example, the westmost tree in the set must be the shortest in the set). The length of the increasing subsequence is the number of trees in it. Note that Liss don't like the trees with the same heights, so it is guaranteed that at any time no two trees have the exactly same heights. The first line contains two integers: n and m (1 xe2 x80 x89 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89105; 1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89m xe2 x80 x89 xe2 x89 xa4 xe2 x80 x892 xc2 xb7105) -- the number of positions and the number of queries. Next m lines contains the information of queries by following formats: The input is guaranteed to be correct, i.e., In each line integers are separated by single spaces. Print m integers -- the length of the longest increasing subsequence after each query. Separate the numbers by whitespaces. States of street after each query you can see on the following animation: If your browser doesn't support animation png, please see the gif version here: http://212.193.37.254/codeforces/images/162/roadtree.gif"...