#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1000000000 + 7;
const long long int MOD1 = 998244353;
long long int pwr(long long int a, long long int b) {
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a *= a;
    b >>= 1;
  }
  return res;
}
const long long int sss = pwr(2, 32);
long long int strTo(string s) {
  stringstream tmp(s);
  long long int x = 0;
  tmp >> x;
  return x;
}
string NoTo(long long int n) {
  ostringstream str1;
  str1 << n;
  string ans = str1.str();
  return ans;
}
vector<bool> sieve(4000001, true);
void Sieve() {
  sieve[0] = false;
  sieve[1] = false;
  for (long long int i = 2; i * i <= 4000000; i++) {
    if (sieve[i] == true) {
      for (long long int j = i * i; j <= 4000000; j += i) sieve[j] = false;
    }
  }
}
long long int nCr(long long int n, long long int r) {
  long long int ans = 1;
  for (long long int i = (long long int)0; i < (long long int)r; i++) {
    ans = (ans * (n - i));
    ans = (ans / (i + 1));
  }
  return ans;
}
long long int pwrm(long long int a, long long int b, long long int m) {
  a %= m;
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
vector<long long int> adj[300010];
long long int dista[100001];
long long int vis[300010];
long long int par[300001];
long long int cl[100001];
long long int sz = 1;
long long int n, q;
long long int arr[10000001];
void init(long long int n) {
  while (sz < n) sz *= 2;
}
vector<long long int> sum(10000010);
void build(long long int a[], long long int x, long long int l,
           long long int r) {
  if (r - l == 1) {
    sum[x] = a[l];
    return;
  }
  long long int m = (l + r) / 2;
  build(a, 2 * x + 1, l, m);
  build(a, 2 * x + 2, m, r);
  sum[x] = max(sum[2 * x + 1], sum[2 * x + 2]);
}
void buil(long long int a[], long long int x, long long int l,
          long long int r) {
  build(a, x, l, r);
}
long long int suf(long long int l, long long int r, long long int x,
                  long long int lx, long long int rx) {
  if (lx >= r || l >= rx) return 0;
  if (lx >= l && rx <= r) return sum[x];
  long long int m = (lx + rx) / 2;
  return max(suf(l, r, 2 * x + 1, lx, m), suf(l, r, 2 * x + 2, m, rx));
}
long long int su(long long int l, long long int r, long long int x,
                 long long int lx, long long int rx) {
  return suf(l, r, x, lx, rx);
}
long long int ar[1000010];
long long int get(long long int k) {
  long long int sum = 0;
  while (k >= 1) {
    sum += ar[k];
    k -= k & -k;
  }
  return sum;
}
void update(long long int in, long long int vl) {
  while (in <= 1000010) {
    ar[in] += vl;
    in += in & -in;
  }
}
long long int sizee[200010] = {0};
long long int ctr = 0;
void df(long long int sr) {
  vis[sr] = 1;
  long long int ctr = 0;
  for (auto it : adj[sr]) {
    if (!vis[it]) {
      df(it);
      ctr += (1 + sizee[it]);
    }
  }
  sizee[sr] = ctr;
}
long long int fac[2000010];
unsigned long long modInverse(unsigned long long n, int p) {
  return pwrm(n, p - 2, p);
}
long long int level[300001];
void dfs(long long int sr, long long int pr, long long int pa) {
  vis[sr] = 1;
  level[sr] = pr;
  par[sr] = pa;
  for (auto it : adj[sr]) {
    if (!vis[it]) dfs(it, pr + 1, sr);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  cin >> n;
  for (long long int i = (long long int)0; i < (long long int)1000010; i++)
    ar[i] = 0;
  long double sum = 0;
  sz = 1;
  while (n--) {
    long long int x;
    cin >> x;
    if (x == 1) {
      long long int a, b;
      cin >> a >> b;
      update(1, b);
      update(a + 1, -b);
      sum += (a * b);
    } else if (x == 2) {
      long long int a;
      cin >> a;
      update(sz + 1, a);
      update(sz + 2, -a);
      sz++;
      sum += a;
    } else {
      long long int tmp = get(sz);
      update(sz, -tmp);
      update(sz + 1, tmp);
      sz--;
      sum -= tmp;
    }
    long double ans = sum / sz;
    cout << fixed << setprecision(6) << ans << "\n";
  }
  cerr << "Time Elapsed : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC
       << "ms\n";
  return 0;
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

Bessie and the cows are playing with sequences and need your help. They start with a sequence, initially containing just the number 0, and perform n operations. Each operation is one of the following:

  1. Add the integer xi to the first ai elements of the sequence. 
  2. Append an integer ki to the end of the sequence. (And hence the size of the sequence increases by 1) 
  3. Remove the last element of the sequence. So, the size of the sequence decreases by one. Note, that this operation can only be done if there are at least two elements in the sequence. 



After each operation, the cows would like to know the average of all the numbers in the sequence. Help them!

Input

The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of operations. The next n lines describe the operations. Each line will start with an integer ti (1 ≤ ti ≤ 3), denoting the type of the operation (see above). If ti = 1, it will be followed by two integers ai, xi (|xi| ≤ 103; 1 ≤ ai). If ti = 2, it will be followed by a single integer ki (|ki| ≤ 103). If ti = 3, it will not be followed by anything.

It is guaranteed that all operations are correct (don't touch nonexistent elements) and that there will always be at least one element in the sequence.

Output

Output n lines each containing the average of the numbers in the sequence after the corresponding operation.

The answer will be considered correct if its absolute or relative error doesn't exceed 10 - 6.

Examples

Input

5
2 1
3
2 3
2 1
3


Output

0.500000
0.000000
1.500000
1.333333
1.500000


Input

6
2 1
1 2 20
2 2
1 2 -3
3
3


Output

0.500000
20.500000
14.333333
12.333333
17.500000
17.000000

Note

In the second sample, the sequence becomes <image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1000000000 + 7;
const long long int MOD1 = 998244353;
long long int pwr(long long int a, long long int b) {
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a *= a;
    b >>= 1;
  }
  return res;
}
const long long int sss = pwr(2, 32);
long long int strTo(string s) {
  stringstream tmp(s);
  long long int x = 0;
  tmp >> x;
  return x;
}
string NoTo(long long int n) {
  ostringstream str1;
  str1 << n;
  string ans = str1.str();
  return ans;
}
vector<bool> sieve(4000001, true);
void Sieve() {
  sieve[0] = false;
  sieve[1] = false;
  for (long long int i = 2; i * i <= 4000000; i++) {
    if (sieve[i] == true) {
      for (long long int j = i * i; j <= 4000000; j += i) sieve[j] = false;
    }
  }
}
long long int nCr(long long int n, long long int r) {
  long long int ans = 1;
  for (long long int i = (long long int)0; i < (long long int)r; i++) {
    ans = (ans * (n - i));
    ans = (ans / (i + 1));
  }
  return ans;
}
long long int pwrm(long long int a, long long int b, long long int m) {
  a %= m;
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
vector<long long int> adj[300010];
long long int dista[100001];
long long int vis[300010];
long long int par[300001];
long long int cl[100001];
long long int sz = 1;
long long int n, q;
long long int arr[10000001];
void init(long long int n) {
  while (sz < n) sz *= 2;
}
vector<long long int> sum(10000010);
void build(long long int a[], long long int x, long long int l,
           long long int r) {
  if (r - l == 1) {
    sum[x] = a[l];
    return;
  }
  long long int m = (l + r) / 2;
  build(a, 2 * x + 1, l, m);
  build(a, 2 * x + 2, m, r);
  sum[x] = max(sum[2 * x + 1], sum[2 * x + 2]);
}
void buil(long long int a[], long long int x, long long int l,
          long long int r) {
  build(a, x, l, r);
}
long long int suf(long long int l, long long int r, long long int x,
                  long long int lx, long long int rx) {
  if (lx >= r || l >= rx) return 0;
  if (lx >= l && rx <= r) return sum[x];
  long long int m = (lx + rx) / 2;
  return max(suf(l, r, 2 * x + 1, lx, m), suf(l, r, 2 * x + 2, m, rx));
}
long long int su(long long int l, long long int r, long long int x,
                 long long int lx, long long int rx) {
  return suf(l, r, x, lx, rx);
}
long long int ar[1000010];
long long int get(long long int k) {
  long long int sum = 0;
  while (k >= 1) {
    sum += ar[k];
    k -= k & -k;
  }
  return sum;
}
void update(long long int in, long long int vl) {
  while (in <= 1000010) {
    ar[in] += vl;
    in += in & -in;
  }
}
long long int sizee[200010] = {0};
long long int ctr = 0;
void df(long long int sr) {
  vis[sr] = 1;
  long long int ctr = 0;
  for (auto it : adj[sr]) {
    if (!vis[it]) {
      df(it);
      ctr += (1 + sizee[it]);
    }
  }
  sizee[sr] = ctr;
}
long long int fac[2000010];
unsigned long long modInverse(unsigned long long n, int p) {
  return pwrm(n, p - 2, p);
}
long long int level[300001];
void dfs(long long int sr, long long int pr, long long int pa) {
  vis[sr] = 1;
  level[sr] = pr;
  par[sr] = pa;
  for (auto it : adj[sr]) {
    if (!vis[it]) dfs(it, pr + 1, sr);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  cin >> n;
  for (long long int i = (long long int)0; i < (long long int)1000010; i++)
    ar[i] = 0;
  long double sum = 0;
  sz = 1;
  while (n--) {
    long long int x;
    cin >> x;
    if (x == 1) {
      long long int a, b;
      cin >> a >> b;
      update(1, b);
      update(a + 1, -b);
      sum += (a * b);
    } else if (x == 2) {
      long long int a;
      cin >> a;
      update(sz + 1, a);
      update(sz + 2, -a);
      sz++;
      sum += a;
    } else {
      long long int tmp = get(sz);
      update(sz, -tmp);
      update(sz + 1, tmp);
      sz--;
      sum -= tmp;
    }
    long double ans = sum / sz;
    cout << fixed << setprecision(6) << ans << "\n";
  }
  cerr << "Time Elapsed : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC
       << "ms\n";
  return 0;
}

```