3640 - Triples of Even Parity

Created by Frank Arteaga Salgado, Roberto Carlos Abreu
Added by frankr (2016-05-21)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Frank likes to play around with integers. When he is bored, he usually starts generating a list of integers in order to perform interesting observations on it.

He starts with an empty list. He can either modify the list, or perform an observation on it. He established the following rules for modifying the list:
  1. Add a new element to the list. He does not like to repeat himself. If the element to be added already exists in the list, then he does not add it again.
  2. Remove an element from the list. Frank does not have the best memory in the world. If the element to be removed does not belong to the list, then nothing gets removed.
Today, Frank's observations on the list are related to counting. Specifically, at any point of his boredom, he would like to know the number of ways in which three different elements from the list can be chosen so that their sum is even. Order is not important to Frank. If, for example, the list at a certain point is (1, 2, 3, 4), then (1, 2, 3) and (1, 3, 2) are considered to be the same.

Frank has requested your help. Write a program that reads the sequence of events of Frank's boredom and computes what Frank needs.
A Frank le encanta jugar con números enteros. Usualmente, cuando está aburrido, Frank genera una lista de enteros para efectuar observaciones interesantes sobre ella.

Frank inicia con una lista vacía. Él puede modificarla o efectuar una observación interesante sobre ella. Para modificarla, Frank estableció las siguientes operaciones:
  1. Añadir un elemento nuevo. A él no le gusta repetirse, así que, si el elemento a añadir ya existe en la lista, Frank no lo añade nuevamente.
  2. Eliminar un elemento. Como Frank no tiene la mejor memoria del mundo, es posible que él intente eliminar un elemento que no existe en la lista. En estos casos, él simplemente ignora y no elimina nada.
En el día de hoy, las observaciones de Frank están relacionadas con conteo. Específicamente, cuando Frank hace una observación, este desea conocer la cantidad de formas posibles de seleccionar tres elementos distintos de la lista de forma tal que su suma sea par. El orden no es un asunto importante para Frank. Si, por ejemplo, la lista es (1, 2, 3, 4), entonces seleccionar (1, 2, 3) y (1, 3, 2) es lo mismo.

Frank te ha pedido tu ayuda. Escribe un programa que procese la secuencia de eventos del aburrimiento de Frank y compute lo requerido.
Frank likes to play around with integers. When he is bored, he usually starts generating a list of integers in order to perform interesting observations on it.

He starts with an empty list. He can either modify the list, or perform an observation on it. He established the following rules for modifying the list:
  1. Add a new element to the list. He does not like to repeat himself. If the element to be added already exists in the list, then he does not add it again.
  2. Remove an element from the list. Frank does not have the best memory in the world. If the element to be removed does not belong to the list, then nothing gets removed.
Today, Frank's observations on the list are related to counting. Specifically, at any point of his boredom, he would like to know the number of ways in which three different elements from the list can be chosen so that their sum is even. Order is not important to Frank. If, for example, the list at a certain point is (1, 2, 3, 4), then (1, 2, 3) and (1, 3, 2) are considered to be the same.

Frank has requested your help. Write a program that reads the sequence of events of Frank's boredom and computes what Frank needs.

Input specification

The first line contains a single integer Q (1 ≤ Q ≤ 105), the number of events in Frank's boredom. Q lines follow. In each of them, an event of Frank's boredom will be presented. The format of events related to manipulation of the list is as follows:
  • <event-type> X
<event-type> will be i if Frank wants to add element X (-109 X 109) to the list, or r, if Frank wants to delete X from the list. If Frank wants to perform an observation, then the line will solely contain q. All events are given in the order in which Frank thought of them.
La primera línea contiene un único entero Q (1 ≤ Q ≤ 105), la cantidad de eventos en el aburrimiento de Frank. Le siguen Q líneas. Cada una de ellas contiene un evento del aburrimiento de Frank. El formato de los eventos relacionados con modificación de la lista es el siguiente:
  • <tipo-evento> X
<tipo-evento> es i si Frank quiere añadir el elemento X (-109 <= X <= 109) a la lista, o r, si Frank quiere eliminar X de la lista. Si Frank quiere hacer una observación, entonces la línea contendrá únicamente la letra q. Todos los eventos se dan en el orden en el cual Frank los pensó.
The first line contains a single integer Q (1 ≤ Q ≤ 105), the number of events in Frank's boredom. Q lines follow. In each of them, an event of Frank's boredom will be presented. The format of events related to manipulation of the list is as follows:
  • <event-type> X
<event-type> will be i if Frank wants to add element X (-109 X 109) to the list, or r, if Frank wants to delete X from the list. If Frank wants to perform an observation, then the line will solely contain q. All events are given in the order in which Frank thought of them.

Output specification

For each observation event, output in a single line the answer according to the current state of the list.
Por cada evento de observación, imprime una línea con la respuesta al conteo de acuerdo al estado actual de la lista.
The first line contains a single integer Q (1 ≤ Q ≤ 105), the number of events in Frank's boredom. Q lines follow. In each of them, an event of Frank's boredom will be presented. The format of events related to manipulation of the list is as follows:
  • <event-type> X
<event-type> will be i if Frank wants to add element X (-109 X 109) to the list, or r, if Frank wants to delete X from the list. If Frank wants to perform an observation, then the line will solely contain q. All events are given in the order in which Frank thought of them.

Sample input

7
q
i 1
i 2
i 3
q
r 3
q

Sample output

0
1
0

Hint(s)

http://coj.uci.cu/contest/
http://coj.uci.cu/contest/
http://coj.uci.cu/contest/