Степан був на книжковому ярмарку і купив книги. Привабливість ~i~-ї книги — ~k_і~. Степан розташував книги на полиці відповідно до їх привабливості, тому перша книга зліва є найменш привабливою, а кожна наступна праворуч більш або однаково приваблива, ніж попередня.

Після покупок минуло чимало часу і Степан лише зараз знайшов час прочитати книжки. Загалом він витратить на читання ~t~ хвилин.

Кожну книгу він може або прочитати повністю, що займе ~a~ хвилин; або читати лише вміст з обкладинок, що займає у нього ~b~ хвилин.

Він почне з крайньої лівої книги. Закінчивши поточну книгу (повністю або лише вміст обкладинок), він переходить до наступної книги, яка є першою праворуч від книги, яку він щойно прочитав. Натхнення Степана дорівнює сумі привабливих цінностей книг, які він прочитав повністю. Яке максимальне значення натхнення Степана через ~t~ хвилин?

Примітка: якщо Степан починає читати книгу, але не закінчує її до закінчення ~t~ хвилин, ця книга не сприяє його натхненню.

Формат вхідних даних

Перший рядок містить цілі числа ~n~, ~t~, ~a~ і ~b~ (~1 ≤ n ≤ 2 · 10^5~, ~1 ≤ t ≤ 10^9~, ~1 ≤ b < a ≤ 10^9~), кількість книжок, час, який Степан витратить на читання, необхідний час для читання книги та час, необхідний для читання вмісту з обкладинок.

У другому рядку міститься ~n~ цілих чисел ~k_i~ (~1 ≤ k_i ≤ 10^9~, ~k_i ≤ k_{i+1}~), значення привабливості книг.

Формат вихідних даних

У першому й єдиному рядку виведіть максимальне натхнення Степана через ~t~ хвилин читання.

Оцінювання

• тести 1-3 - 0 балів
• тести 4-10 (~k_i=k_{i+1}~)- 20 балів
• тести 11-20 (~n \le 1000~) - 30 балів
• тести 21-28 (без додаткових обмежень) - 50 балів

Приклад вхідних даних

3 5 2 1 
2 2 4

Приклад вихідних даних

6

Приклад вхідних даних

2 10 3 1 
3 3

Приклад вихідних даних

6

Приклад вхідних даних

4 10 3 2
3 4 5 6

Приклад вихідних даних

12

Маленька Оксі отримала у подарунок деревʼяну рамку у формі правильного багатокутника. Оскільки багатокутник має ~n~ вершин, він містить ~(n \times (n-3))/2~ деревʼяних паличок, які відповідають кожній можливій діагоналі. Вершини багатокутника позначені цілими числами від 1 до ~n~ проти годинникової стрілки. Спочатку Оксі розташувала ~n-3~ палички всередині рамки таким чином, що кожна паличка торкається двох несусідніх вершин рамки, і ніякі дві палички не перетинаються. Іншими словами, вона зробила тріангуляцію. Оскільки це було недостатньо цікаво для неї, вона вирішила пограти з цією конфігурацією, застосувавши певну операцію, яка складається з двох кроків:

• Зніміть паличку.
• Додаємо нову паличку таким чином, щоб отримати нову тріангуляцію.

Ми характеризуємо операцію впорядкованою парою невпорядкованих пар ~((a, b), (c, d))~, що означає, що маленька Оксі видалила паличку, яка торкається вершин ~a~ і ~b~, і додала паличку, що торкається вершин ~c~ і ~d~.

Оксі любить віяла, тому, виконуючи ці операції, вона іноді запитує себе: «Скільки операцій потрібно, щоб перетворити цю тріангуляцію на «віялову» тріангуляцію у вершині ~x~, і скількома способами це можливо зробити?».

Оскільки маленька Оксі зайнята операціями та розважається, то вона просить вашої допомоги!

«Віялова» тріангуляція у вершині ~x~ - це тріангуляція, де всі діагоналі мають спільну кінцеву точку, а саме вершину ~х~.

Нехай кількість необхідних операцій дорівнює ~m~. Нехай ~f_1, f2, . . . , f_m~ - це послідовність операцій, які при застосуванні в заданому порядку досягають бажаної тріангуляції, таким чином представляючи один із шляхів досягнення цього. Нехай ~s_1, s_2, . . . , s_m~ є іншою такою послідовністю. Дві послідовності є різними, якщо існує такий індекс ~i~, що ~f_i \neq s_i~.

Оскільки кількість таких послідовностей може бути дуже багато, то маленьку Оксі цікавить лише її залишок від ділення за модулем ~10^9 + 7~.

Формат вхідних даних

У першому рядку цілі числа ~n~ і ~q~ (~4 ≤ n ≤ 2·10^5~,~1 ≤ q ≤ 2·10^5~), кількість вершин і кількість подій

У кожному з наступних ~n - 3~ рядків записані цілі числа ~x_i, y_i~ (~1 ≤ x_i, y_i ≤ n~) — мітки вершин, яких торкається ~i~-та паличка.

У кожному з наступних ~q~ рядків є ціле число ~t_i~ (~1 ≤ t_i ≤ 2~), яке представляє тип події. Якщо ~t_i = 1~, за ним йдуть 4 цілі числа ~a_i, b_i, c_i, d_i~ (~1 ≤ a_i, b_i, c_i, d_i ≤ n~), які означають операцію ~((a_i, b_i), (c_i, d_i)~, яка виконується в цей момент. Гарантовано, що дана операція може бути реалізована. Якщо ~t_i = 2~, за ним йде ціле число ~x_i~ (~1 ≤ x_i ≤ n~), що означає, що маленьку Оксі цікавлять дані для «віялової» тріангуляції у вершині ~x_i~ по відношенню до поточної тріангуляції.

Формат вихідних даних

Для кожної події типу 2, у порядку їх надходження на вхід, виведіть два цілі числа: мінімальну кількість необхідних операцій і кількість способів дістатися до цільової тріангуляції за допомогою мінімальної кількості операцій.

Оцінювання

• тести 1-3 - 0 балів
• тести 4-13 (~n≤9,q≤1000~) - 10 балів
• тести 14-21 (~x_i =1,y_i =i+2~ для ~i=1,...,n-3~ і подій типу 1 немає - 15 балів
• тести 22-29 (~q=1~) - 25 балів
• тести 30-41 (~n,q ≤ 1000~) - 10 балів
• тести 42-55 (Жодних додаткових обмежень) - 40 балів

Пояснення

До першого прикладу: Початок тріангуляції вже є «віяльною» тріангуляцією у вершині 1, тому маленька Оксі не повинна виконувати жодних операцій, щоб можна зробити одним способом. Після виконання даної операції тепер є лише один спосіб повернути її до попереднього стану, а саме застосувати операцію ~((2, 4), (1, 3))~.

До другого прикладу: Єдина послідовність операцій для першого запиту: ~((3, 5), (1, 4))~.

Єдина послідовність операцій для другого запиту: ~((1, 3), (2, 5))~, ~((3, 5), (2, 4))~.

Єдина послідовність операцій для третього запиту: ~((3, 5), (2, 5))~.

Приклад вхідних даних

4 3
1 3
2 1
1 1 3 2 4
2 1

Приклад вихідних даних

0 1
1 1

Приклад вхідних даних

5 4
1 3
3 5
2 1
2 2
1 1 3 2 5
2 2

Приклад вихідних даних

1 1
2 1
1 1

Приклад вхідних даних

9 3
1 5
1 7
2 4
2 5
5 7
7 9
2 1
1 2 5 1 4
2 1

Приклад вихідних даних

4 12
3 6

Степан нарешті дочекався щорічної відпустки. Країну, куди він вирішив помандрувати, можна представити у вигляді ~n~ міст і ~m~ двонаправлених доріг, що їх зʼєднують. Кожна дорога має однакову довжину, і можна дістатися будь-якого міста з будь-якого іншого, подорожуючи цими дорогами. Шлях від міста ~a~ до міста ~b~ визначається як послідовність доріг, що, починаючи з міста ~a~ і послідовно проходячи дороги в цій послідовності, потрапляє в місто ~b~. Довжина шляху визначається як кількість доріг на цьому шляху.

Степан зазвичай бронював найдорожчий готель в одному з міст, а потім починав планувати свою подорож. Щоб полегшити планування, він записав довжину найкоротшого шляху від готелю до кожного міста.

У захваті від довгоочікуваної відпустки Степан зовсім забув, у якому місті знаходиться готель. Він точно не хоче пропускати поїздку, тому просить вас визначити, в яких містах може бути розташований готель.

Формат вхідних даних

У першому рядку — натуральні числа ~n~ і ~m~ — кількість міст і кількість доріг, що їх зʼєднують (~1 ≤ n ≤ 5 · 10^4~, ~n-1 ≤ m ≤ 10^5~).

В ~i~-му з наступних ~m~ рядків є числа ~u_i~ та ~v_i~ - є дорога між містами ~u_i~ та ~v_i~ (~1 ≤ u_i, v_i ≤ n~, ~u_i \neq v_i~). Між будь-якими двома містами існує щонайбільше одна дорога.

В останньому рядку ~n~ цілих чисел - ~i~-те число ~d_i~ вказує на відстань від ~i~-го міста до міста, де розташований готель, або -1, якщо Степан не записав цю відстань (~-1 ≤ d_i < n~).

Формат вихідних даних

У першому рядку напишіть кількість міст, де може бути розташований готель.

У другому рядку запишіть у порядку зростання міста, де може розташовуватися готель.

Оцінювання

• 10 балів ~m+1=n≤5000~,~u_i+1=v_i~
• 20 балів ~d_i =-1~ для ~i>1~
• 30 балів ~n,m≤5000~
• 40 балів Без додаткових обмежень.

Пояснення до першого прикладу:

Шлях із міста 4 до міста 1 має довжину 2, тоді як шлях із міста 4 до міста 7 має довжину 3. Таким чином, місто 4 задовольняє обом умовам, і готель може бути розташований там. Те саме стосується міста, позначеного цифрою 6.

Приклад вхідних даних

7 6
1 2
1 3
3 4
3 5
3 6
5 7
2 -1 -1 -1 -1 -1 3

Приклад вихідних даних

2
4 6

Приклад вхідних даних

6 6
1 2
2 3
3 4
4 5
5 6
6 1
2 -1 -1 1 -1 -1

Приклад вихідних даних

2
3 5

Приклад вхідних даних

4 3
1 2
2 3
3 4
1 -1 -1 1

Приклад вихідних даних

0

Степан, любитель настільних ігор, нещодавно відкрив для себе гру Robots. Гра складається з дошки з ~n~ рядків і ~m~ стовпців і одного робота. Поле (1, 1) є верхнім лівим полем дошки, тоді як поле (~n, m~) є нижнім правим.

На початку робот розташовується на якомусь полі ~(x,y)~ (~x~-й рядок, ~y~-й стовпець), і гравець може направляти його в одному з чотирьох напрямків: вгору, вниз, вліво або вправо. Залежно від обраного напрямку, він буде рухатися в цьому напрямку, поки не зустріне свою ціль або спеціальне поле на дошці. Якщо в будь-який момент він на краю дошки і хоче вийти з дошки, він обертається на іншу сторону дошки. Наприклад, якщо він знаходиться на полі (~n, 3~) і хоче рухатися вниз, він прибуде на поле (1, 3).

На дошці є три типи полів:

• Порожнє поле - робот продовжує рух у тому ж напрямку
• Поле повороту вліво - коли робот ступить на це поле, він поверне ліворуч на 90° і продовжить рух
• Поле повороту вправо - коли робот наступить на це поле, він повернеться вправо на 90° і продовжить рух

Більшість полів на дошці порожні, лише ~k~ з них є полями повороту ліворуч або праворуч.

Гра складається з ~q~ раундів. В ~і~-му раунді гри робот буде розміщений на полі (~a_i,b_i~). Мета полягає в тому, щоб досягти поля (~c_i,d_i~), використовуючи мінімальну кількість ходів, або визначити, що це зробити неможливо.

Погравши в цю гру кілька разів, Степан зрозумів, що вона складніша, ніж здавалося спочатку. Ось чому йому зараз потрібна ваша допомога. Допоможіть йому визначити мінімальну кількість ходів, необхідну для кожного раунду гри!

Примітка: якщо робот починає або закінчує свій шлях на полі повороту ліворуч або праворуч, цей поворот не зараховується.

Формат вхідних даних

У першому рядку записано цілі числа ~n~, ~m~ і ~k~ (~1 ≤ n, m ≤ 10^6~, ~0 ≤ k ≤ 10^5~), кількість рядків, стовпців і непорожніх полів на дошці.

~i~-й із наступних ~n~ рядків містить цілі числа ~x_i,y_i~ та символ ~s_i~ (~1 ≤ x_i ≤ n~,~1 ≤ y_i ≤ m~,~s_i = ʼLʼ~ або ~s_i = ʼRʼ~), рядок і стовпець ~i~-го поля й тип повороту. Якщо ~s_i = «L»~, то слід повернути ліворуч. Якщо ~s_i = «R»~, то це поле повороту праворуч.

Наступний рядок містить ціле число ~q~ (~1 ≤ q ≤ 3 · 10^5~), кількість раундів.

~I~-й із наступних ~q~ рядків містить цілі числа ~a_i, b_i, c_i, d_i~(~1 ≤ a_i, c_i ≤ n~, ~1 ≤ b_i, d_i ≤ m~), стартову позицію та цільову клітину.

Формат вихідних даних

В ~i~-му з наступних ~q~ рядків вивести мінімальну кількість ходів для ~i~-го раунду гри або -1, якщо неможливо досягти мети.

Оцінювання

• тести 1-3 - 0 балів
• тести 4-7 - 10 балів ~k=0~
• тести 8-21 - 15 балів ~n,m≤300,q≤10~
• тести 22-35 - 45 балів ~n,m ≤ 300~
• тести 36-47 - 30 балів Жодних додаткових обмежень.

Приклад вхідних даних

2 2 2
1 1 L
2 2 R
5
1 1 2 2
2 1 1 2
1 1 1 2
2 1 1 1
2 2 2 1

Приклад вихідних даних

-1
1
0
0
0

Приклад вхідних даних

3 3 4
1 1 L
1 3 L
2 1 L
3 3 L
7
1 1 3 3
3 3 2 1
3 1 2 2
2 3 1 2
2 3 3 1
1 2 3 2
3 3 2 2

Приклад вихідних даних

1
2
1
1
1
0
3

Приклад вхідних даних

4 4 8
1 1 R
1 3 L
2 2 R
2 4 L
3 1 L
3 3 L
4 2 L
4 4 L
7
1 2 1 4
2 2 3 4
4 4 3 2
4 1 4 4
4 2 3 1
1 2 2 3
2 4 2 3

Приклад вихідних даних

2
1
1
0
-1
5
0