Маємо горизонтальний циліндр.

Дано \(Q\) запитів, обробіть їх у заданому порядку. Кожен запит відноситься до одного з наступних двох типів.

• 1 \(x\) \(c\): Вставте \(c\) кульок з цифрою \(x\), написаною на кожній з них, у правий кінець циліндра.

• 2 \(c\): Вийміть \(c\) крайні ліві кульки, що містяться в циліндрі, і виведіть суму чисел, написаних на вийнятих кульках.

Припустимо, що кульки ніколи не змінюють свого порядку в циліндрі.

Обмеження

• \(1 \leq Q \leq 2 \times 10^5\)

• \(0 \leq x \leq 10^9\)

• \(1 \leq c \leq 10^9\)

• Щоразу, коли дається запит типу 2 \(c\), у циліндрі є \(c\) або більше кульок.

• Усі значення у вхідних даних є цілими числами.

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

Перший рядок містить ціле число \(Q\)

Наступні  \(Q\) рядків містять запити описаних форматів

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

У вихідний потік виведіть відповіді на запити типу 2

Примітка

До прикладу 1:

• Для 1-го запиту вставте 3 кульки з цифрою 2, написаною на кожній, у правий кінець циліндра. Тепер у циліндрі є кульки з числами (2,2,2), написаними на них зліва направо.

• Для 2-го запиту вийміть 2 крайні ліві кулі, що містяться в циліндрі. На вийнятих кульках написані числа 2,2, тобто сума 4. Тепер у циліндрі є кулька з числом (2), написаним на ньому зліва направо.

• Для 3-го запиту вставте 4 кульки з цифрою 3 на кожній з них у правий кінець циліндра. Тепер у циліндрі є кульки з числами (2,3,3,3,3), написаними на них зліва направо.

Для 4-го запиту вийміть 3 крайні ліві кульки, що містяться в циліндрі. На вийнятих кульках написані числа 2,3,3, тобто сума 8. Тепер у циліндрі є кульки з числами (3,3), написаними на них зліва направо.

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

4
1 2 3
2 2
1 3 4
2 3

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

4
8

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

2
1 1000000000 1000000000
2 1000000000

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

1000000000000000000

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

5
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

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