B'You have long dreamed of working in a large IT company and finally got a job there. You have studied all existing modern technologies for a long time and are ready to apply all your knowledge in practice. But then you sit down at your desk and see a sheet of paper with the company 's motto printed in large letters: abcdabcdabcdabcd.... The company 's motto contains four main principles -- a (Willi), b (Nilli), c (Crack), d (Release). Therefore, you consider strings of length n consisting of these four Latin letters. Unordered pairs of letters "ab", "bc", "cd", and "da" in this motto are adjacent, so we will call such pairs of symbols good. So, if you are given a string s of length n , and it is known that the unordered pair of symbols { x, y } is good, then you can perform one of the following operations on the string: For example, the string bacdd can be replaced with one of the strings bacda, bacdc, or badcc, and the string aac can be replaced with aab or aad. A non-empty sequence of operations for the string s will be called correct if the following two conditions are met: Now we are ready to move on to the problem statement! You have a set of strings that is initially empty. Then, each of q queries adds another string t_i to the set, or removes the string t_i from the set. After each query, you need to output the minimum and maximum size of a correct sequence of operations in which each word occurs at least once. The choice of the initial string s is up to you. The first line contains two integers n and q ( 1 <= n <= 20 , 1 <= q <= 100 ,000 ) -- the length of the strings under consideration and the number of queries to modify the set of strings. Each of the next q lines contains a string t_i ( lvert t_i rvert = n ). All strings consist of characters "a", "b", "c" and "d". If the string t_i was not in the set before the query, it is added to the set, '...