Bob had a string ~S~ of length ~N~, consisting only of lowercase letters a and b.

He discovered that the string satisfied ~M~ constraints. Each constraint is a pair of integers ~L~ and ~R~, which means that in the substring ~S[L..R]~ (~1~-based indexing), the number of a characters is equal to the number of b characters.

Unfortunately, Bob lost the string. Your task is to reconstruct a string of length ~N~ that consists only of characters a and b and satisfies all ~M~ constraints. If there are multiple solutions, you need to output the lexicographically smallest one. It is guaranteed that the solution exists.

Input Specification

The first line contains two integers ~N~ and ~M~ (~2 \le N \le 10^6~, ~1 \le M \le 2 \times 10^5~), the length of the string and the number of constraints.

Each of the following ~M~ lines contains two integers ~L~ and ~R~ (~1 \le L < R \le N~), representing a constraint as described above. It is guaranteed that ~R - L + 1~ is even.

Output Specification

Output a string of length ~N~, consisting of a and b, that satisfies all the given constraints and is lexicographically smallest.

Constraints

Subtask	Points	Additional constraints
~1~	~20~	~N, M \le 20~
~2~	~80~	No additional constraints

Sample Input

6 2
1 4
3 6

Sample Output

aabbaa

Explanation for Sample

aabbaa is the lexicographically smallest string which satisfies the given two constraints.