Transit Gate Trip Time Average

A transit system records rider journeys between stations. It processes q operations, each one of:

• IN id station t — rider id enters at station at time t. The rider is not currently in transit.
• OUT id station t — rider id exits at station at time t. It is guaranteed the rider previously entered and has not yet exited; the exit time is at least the entry time. This completes one trip from the entry station to station lasting (exit time - entry time).
• AVG from to — report the average duration of all completed trips whose start station is from and end station is to, truncated down to an integer (floor). It is guaranteed at least one such trip has completed.

Station names and ids are non-empty tokens of lowercase letters and digits.

Input format

Line 1: an integer q. Next q lines: IN id station t, OUT id station t, or AVG from to.

Output format

For each AVG operation, in order, print the floored average trip duration.

Constraints

• 1 <= q <= 40
• 0 <= t <= 1000000
• 1 <= length of id, station <= 12