В городе Каскелен есть n горизонтальных и n вертикальных улиц которые образуют форму решетки. Пронумеруем горизонтальные улицы с севера на юг, а вертикальные улицы с запада на восток от 1 до n. Обозначим перекресток (i,j), как перекресток на пересечении i-й горизонтальной и j-й вертикальной улиц.
Поскольку в Каскелене загруженные дороги, администрация города решила сделать все улицы односторонними. Подобная реформа, хоть и уменьшает трафик, имеет несколько недостатков. Во первый, Каскелен это быстрорастущий город и администрации часто приходится менять направления улиц. Во вторых, иногда может оказаться что часть города отделена от других и становится невозможно добраться от одной точки города до другой.
Чтобы услеживать за подобными изменениями вас попросили написать программу которая моделирует систему улиц города. Вам нужно уметь обрабатывать запросы трех видов:
• 1 r₁ c₁ r₂ c₂ — Проверьте можно ли добраться из перекрестка (r₁,c₁) в перекресток (r₂,c₂).
• 2 r — Меняется направление движения горизонтальной улицы r на противоположное.
• 3 c — Меняется направление движения вертикальной улицы c на противоположное.
Формат входных данных
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t (1 ≤ t ≤ 1000) — количество наборов входных данных.
Первая строка набора содержит два целых числа n и q (2 ≤ n ≤ 3·10⁵, 1 ≤ q ≤ 3·10⁵) — количество горизонтальных/вертикальных улиц и количество запросов.
Вторая строка набора содержит одну строку a длины n — описание горизонтальных дорог. Если aᵢ = 'L', то i-я улица направлена с востока на запад. Если aᵢ = 'R', то c запада на восток.
Третья строка набора содержит одну строку b длины n — описание вертикальных дорог. Если bᵢ = 'U', то i-я улица направлена с юга на север, иначе если bᵢ = 'D', то c севера на юг.
Каждая из следующих q строк содержит запрос, который задан в формате, описанном в условии задачи.
Формат выходных данных
Для каждого запроса первого типа, выведите «YES» если можно добраться из первого перекрестка во второй. Иначе, выведите «NO».