魔王大人的打工日常
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

魔王撒旦最近在730餐厅打工, 今天店长交给了魔王大人 n 个碟子, 每个碟子大小都不一样, 且大小都在区间[1,n]内, 刚开始碟子的排列是 P=(1,2,⋯,n-1,n), 排列中每个数代表碟子的大小, 现在店长要求魔王大人按照给定顺序对碟子进行重新排列, 有 m 次操作, 每次操作要求对在第 l 个到第 r 个碟子这个区间的碟子进行 k 次循环右移.

魔王大人前几天在勇者艾米莉亚那里学到了关于碟子排列的一些知识, 设a_i为第 i 个碟子的大小, 我们称一个逆序对为碟子的排列中满足 a_i>a_j且i<j 的盘子二元组(i,j), 业界普遍认为逆序对数为偶数的碟子排列是一个好排列, 逆序对数为奇数的碟子排列是一个差排列. 现在魔王大人想在每一次无聊的操作后, 判断一下目前碟子的排列是不是一个好的排列, 但是这太费时间了, 于是麻烦你写个程序在每次操作后判断一下碟子的排列是不是一个好排列.

NOTE:对在第 l 个到第 r 个碟子这个区间的碟子 P'=(p_{l},p_{{l+1}},...,p_{{r-1}},p_{r}) 的一次循环右移操作使得 P'=(p_{r},p_{l},p_{{l+1}}...,p_{{r-1}}).


输入描述:

第一行两个整数 n , m (1≤n,m≤100000), 表示碟子的个数和操作次数;
第二行至第m+1行,\ 每行给定操作区间左端点l和右端点r 和循环右移次数k,保证l<=r且k>0.保证k在int范围内.

输出描述:

有 m 行输出，第 i 行输出代表第 i 次操作后的碟子排列的好坏,如果排列为一个好的排列输出"hao",否则输出"huai".
示例1

输入

复制 
5 2
2 5 1
1 4 2

输出

复制 
huai
huai
示例2

输入

复制 
10 10
5 9 7
1 3 1
1 10 9
5 9 8
8 10 5
2 9 3
5 5 6
2 9 5
6 6 10
8 10 3

输出

复制 
hao
hao
huai
huai
huai
hao
hao
huai
huai
huai

备注:

对第一组样例的解释:
初始排列P=(1,2,3,4,5),
第一次操作后排列P=(1,5,2,3,4),逆序对有(5,2),(5,3),(5,4)共3对,为差排列.
第二次操作后排列P=(2,3,1,5,4),逆序对有(2,1),(3,1),(5,4)共3对,为差排列.