B. Идеально сбалансированная строка?
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовём строку $$$s$$$ идеально сбалансированной, если для всех возможных троек $$$(t,u,v)$$$ таких, что $$$t$$$ является непустой подстрокой $$$s$$$, а $$$u$$$ и $$$v$$$ являются символами, присутствующими в $$$s$$$, разница в количествах вхождений $$$u$$$ и $$$v$$$ в $$$t$$$ отличается не более, чем на $$$1$$$.

Например, строки «aba» и «abc» являются идеально сбалансированными, а «abb» нет, потому что для тройки («bb»,'a','b') условие не выполняется.

Вам дана строка $$$s$$$, состоящая только из строчных латинских букв. Ваша задача состоит в том, чтобы определить, является ли $$$s$$$ идеально сбалансированной или нет.

Строка $$$b$$$ называется подстрокой строки $$$a$$$, если $$$b$$$ может быть получена удалением нескольких (возможно $$$0$$$) символов из начала и нескольких (возможно $$$0$$$) символов из конца $$$a$$$.

Входные данные

Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1\leq t\leq 2\cdot 10^4$$$) — количество наборов входных данных.

Каждая из следующих $$$t$$$ строк содержит единственную строку $$$s$$$ ($$$1\leq |s|\leq 2\cdot 10^5$$$), состоящую из строчных букв латинского алфавита.

Гарантируется, что сумма $$$|s|$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если $$$s$$$ является идеально сбалансированной, и «NO» иначе.

Вы можете выводить каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).

Пример
Входные данные
5
aba
abb
abc
aaaaa
abcba
Выходные данные
YES
NO
YES
YES
NO
Примечание

Пусть $$$f_t(c)$$$ обозначает количество вхождений символа $$$c$$$ в строку $$$t$$$.

Для первого набора входных данных получается:

$$$t$$$$$$f_t(a)$$$$$$f_t(b)$$$
$$$a$$$$$$1$$$$$$0$$$
$$$ab$$$$$$1$$$$$$1$$$
$$$aba$$$$$$2$$$$$$1$$$
$$$b$$$$$$0$$$$$$1$$$
$$$ba$$$$$$1$$$$$$1$$$
Можно увидеть, что для любой подстроки $$$t$$$ в $$$s$$$, разница между $$$f_t(a)$$$ и $$$f_t(b)$$$ не превышает $$$1$$$. Значит, строка $$$s$$$ идеально сбалансирована.

Для второго набора входных данных получается:

$$$t$$$$$$f_t(a)$$$$$$f_t(b)$$$
$$$a$$$$$$1$$$$$$0$$$
$$$ab$$$$$$1$$$$$$1$$$
$$$abb$$$$$$1$$$$$$2$$$
$$$b$$$$$$0$$$$$$1$$$
$$$bb$$$$$$0$$$$$$2$$$
Можно увидеть, что для подстроки $$$t=bb$$$, разница в количествах вхождений $$$f_t(a)$$$ и $$$f_t(b)$$$ равна $$$2$$$, что больше $$$1$$$. Значит, строка $$$s$$$ не идеально сбалансирована.

Для третьего набора входных данных получается:

$$$t$$$$$$f_t(a)$$$$$$f_t(b)$$$$$$f_t(c)$$$
$$$a$$$$$$1$$$$$$0$$$$$$0$$$
$$$ab$$$$$$1$$$$$$1$$$$$$0$$$
$$$abc$$$$$$1$$$$$$1$$$$$$1$$$
$$$b$$$$$$0$$$$$$1$$$$$$0$$$
$$$bc$$$$$$0$$$$$$1$$$$$$1$$$
$$$c$$$$$$0$$$$$$0$$$$$$1$$$

Можно увидеть, что для любой подстроки $$$t$$$ в $$$s$$$ и любых двух символов $$$u,v\in\{a,b,c\}$$$, разница между $$$f_t(u)$$$ и $$$f_t(v)$$$ не превышает $$$1$$$. Значит, строка $$$s$$$ идеально сбалансирована.