Hay \(N\) proveedores; el proveedor \(i\) puede abastecer desde el día \(S_i\) en adelante y cobra \(P_i\) por día. Se cumple \(S_i < S_{i+1}\) y \(P_i > P_{i+1}\).

Se mantiene una base de clientes, inicialmente vacía. El cliente \(j\) quiere abastecimiento hasta el día \(E_j\) inclusive y gana \(R_j\) por día. Si se empareja el proveedor \(i\) con el cliente \(j\) (requiere \(S_i \le E_j\)), la ganancia es \((R_j - P_i) \times (E_j - S_i + 1)\).

Procesa \(Q\) operaciones en orden: agregar un cliente a la base, o consultar, para un proveedor \(i\), la máxima ganancia emparejándolo con un cliente de la base (o \(0\) si ninguna ganancia es positiva). Las consultas no consumen ni al proveedor ni al cliente.

Entrada

La primera línea tiene un entero \(N\) \((1 \le N \le 2 \cdot 10^5)\).

La \(i\)-ésima de las siguientes \(N\) líneas tiene dos enteros \(S_i\) y \(P_i\) \((1 \le S_i, P_i \le 10^9)\). Se garantiza \(S_i < S_{i+1}\) y \(P_i > P_{i+1}\).

La siguiente línea tiene un entero \(Q\) \((1 \le Q \le 2 \cdot 10^5)\), y siguen \(Q\) líneas con las operaciones: c E R \((1 \le E, R \le 10^9)\) agrega un cliente, y s I \((1 \le I \le N)\) consulta el proveedor \(I\). Hay al menos una consulta.

Salida

Para cada consulta s, en orden, una línea con la máxima ganancia.

Ejemplo 1

Entrada

4
2 8
4 5
7 3
9 2
11
s 1
c 10 10
s 1
s 2
s 3
s 4
c 7 26
s 2
s 4
s 3
s 1

Salida

0
18
35
28
16
84
16
28
108

Regional Latinoamericana 2023 del ICPC, problema A («Analyzing Contracts»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.