CF145E Lucky Queries

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not. Petya brought home string $ s $ with the length of $ n $ . The string only consists of lucky digits. The digits are numbered from the left to the right starting with $ 1 $ . Now Petya should execute $ m $ queries of the following form: - switch $ l $ $ r $ — "switch" digits (i.e. replace them with their opposites) at all positions with indexes from $ l $ to $ r $ , inclusive: each digit $ 4 $ is replaced with $ 7 $ and each digit $ 7 $ is replaced with $ 4 $ $ (1

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

For each query count print an answer on a single line.

In the first sample the chronology of string $ s $ after some operations are fulfilled is as follows (the sought maximum subsequence is marked with bold): 1. 47 2. 74 3. 74 In the second sample: 1. 747 2. 447 3. 447 4. 774 5. 774