Перехрестя#411
Відомо, що в Мегаполісі будується об’їздна автомагістраль. Ця автомагістраль не є кільцевою дорогою, тобто має різні західний та східний кінці (хоча у майбутньому це може змінитися). Найцікавішою інженерною особливістю цієї дороги є мости. Зрозуміло, що залізобетонний міст надто дорогий для ділянки, по якій проїжджає лише одна машина на день, тоді як дерев’яний міст не витримає швидкісної автомагістралі з десятками машин за хвилину. Тому для правильного проектування мостів важливо знати, скільки автомобілів проїде ними.
На дорозі планується використовувати переважно розв’язки типу «клевер»; схема такої розв’язки зображена на малюнку. За цією схемою, автомобіль, який повертає праворуч, не проїжджає міст; автомобіль, який повертає ліворуч (у цій розв’язці він виконує поворот праворуч на градусів і перетинається зі своєю траєкторією на другому рівні), завжди проїжджає міст, а автомобіль, що рухається прямо, може проїжджати міст або ні, залежно від напрямку руху.
Потік автомобілів на дорогах, що перетинають об’їзну, досліджено. Потрібно порахувати потік машин, які будуть проїжджати мостами об’їзної. Зверніть увагу, що на деяких розв’язках об’їзна проходить по землі, а міст прокладається над нею — такі мости враховувати не потрібно. Хоча дорога двостороння, у кожному тесті розглядається лише один напрямок руху об’їзної (наприклад, із заходу на схід).
Перший рядок містить кількість тестів.
Перший рядок кожного тесту містить число N \leq 100 — кількість розв’язок у порядку з заходу на схід.
Далі йдуть рядків з інформацією про кожну розв’язку: спочатку зазначено тип перетину латинською літерою: означає, що об’їзна пролягає по землі, а міст — на перехресті зверху; — на землі знаходиться перехрестя, а об’їзна йде по мосту зверху. Далі йдуть числа, які задають кількість машин, що з’їжджають з об’їзної: перше — поворот ліворуч, друге — поворот праворуч. Потім ще числа — скільки машин заїжджає на об’їзну: перше — з поворотом ліворуч, друге — з поворотом праворуч. Для будь-якої розв’язки кількість машин не перевищує 10^9.
Гарантується коректність вхідних даних (спочатку на об’їзній немає машин; кількість машин, що сходять з об’їзної, дорівнює кількості машин, які на неї заходять; східна розв’язка знаходиться після західної).
Для кожного тесту виведіть по одному рядку з числами — потоки машин через мости об’їзної. Якщо об’їзна пролягає по землі, а міст над нею, виведіть .
Приклад 1