Спочатку на числовій прямій немає жодного покриття. Потрібно обробити q запитів виду \(ADD\: l\: r\) додати відрізок [l,r]. Після кожного запиту потрібно знайти найменшу невід'ємну точку, яка не належить жодному відрізку.

Input Specification

Перший рядок містить ціле число \(q\), де \(q\) --- кількість запитів. Наступні \(q\) рядків містять запити \(ADD\: l\: r\), де \(ADD\: l\: r\) --- запит(\(l\), \(r\) --- цілі числа). \(\\1 \leq q \leq 2 \cdot 10^5\\\) \(0 \leq l < r \leq 2 \cdot 10^9\\\)

Output Specification

Після кожного запиту виведіть найменшу невід'ємну непокриту точку.

Sample Input 1

2
ADD 0 3
ADD 4 10

Sample Output 1

4
11

Sample Input 2

4
ADD 5 10
ADD 0 3
ADD 4 6
ADD 0 20

Sample Output 2

0
4
11
21