#include <bits/stdc++.h>
using namespace std;
#define int long long
using namespace std;
int solution(vector<int> &A) {
    int n = A.size();
    int m = 0;
    int i = 0;
    while (i < n - 1) {
        if (A[i] >= A[i + 1]) {
            int j = i + 1;
            while (j < n && A[j] <= A[j - 1]) {
                j++;
            }
                        m++;
                        i = j;
        } else {
            i++;
        }
    }
    
    return m;
}

SELECT 
    c.mac,
    SUM(t.amount) AS traffic,
    ROUND(SUM(t.amount) * c.tariff, 2) AS cost
FROM 
    clients c
JOIN 
    traffic t ON c.id = t.client_id
WHERE 
    t.dt LIKE '2022-05%'
GROUP BY 
    c.mac, c.tariff
ORDER BY 
    cost DESC;

def largest_x(matrix):
    R, C = len(matrix), len(matrix[0])
    lu = [[0]*C for _ in range(R)]
    ru = [[0]*C for _ in range(R)]
    ld = [[0]*C for _ in range(R)]
    rd = [[0]*C for _ in range(R)]
    
    for r in range(R):
        for c in range(C):
            if matrix[r][c]:
                lu[r][c] = 1 + (lu[r-1][c-1] if r and c else 0)
                ru[r][c] = 1 + (ru[r-1][c+1] if r and c < C-1 else 0)
                
    for r in range(R-1, -1, -1):
        for c in range(C):
            if matrix[r][c]:
                ld[r][c] = 1 + (ld[r+1][c-1] if r < R-1 and c else 0)
                rd[r][c] = 1 + (rd[r+1][c+1] if r < R-1 and c < C-1 else 0)
    
    max_size, res = 0, [0,0]
    for r in range(R):
        for c in range(C):
            if matrix[r][c]:
                s = min(lu[r][c], ru[r][c], ld[r][c], rd[r][c])
                if s > max_size or (s == max_size and (r < res[0] or (r == res[0] and c < res[1]))):
                    max_size, res = s, [r, c]
    return res

#include <bits/stdc++.h>
using namespace std;

int l2_ceil(int x) {
    assert(x > 0);
    int r = (x & (x-1)) != 0;
    while (x >>= 1) ++r;
    return r;
}

struct node {
    int v, s, e, lazy;
};

using tree = vector<node>;

int mk_node(vector<node>& t, const vector<int>& l, int s, int e, int n) {
    if (s == e) {
        return (t[n] = {l[s], s, s, 0}).v;
    }

    int m = (s + e) / 2;
    return (t[n] = {max(mk_node(t, l, s, m, 2*n), mk_node(t, l, m+1, e, 2*n+1)), s, e}).v;
}

tree mk_tree(const vector<int>& l) {
    vector<node> r(1 << (l2_ceil(l.size()) + 1));
    mk_node(r, l, 0, l.size() - 1, 1);
    return r;
}

void add_node(vector<node>& t, int s, int e, int x, int k) {
    auto& n = t[k];
    if (s <= n.s && n.e <= e) {
        n.lazy += x;
        return;
    }
    if (n.e < s || e < n.s) return;

    add_node(t, s, e, x, 2*k);
    add_node(t, s, e, x, 2*k+1);
    n.v = max(t[2*k].v + t[2*k].lazy, t[2*k+1].v + t[2*k+1].lazy);
}

int query_node(vector<node>& t, int s, int e, int k) {
    auto& n = t[k];
    if (s <= n.s && n.e <= e) return n.v + n.lazy;
    if (n.e < s || e < n.s) return numeric_limits<int>::min();

    if (n.lazy) {
        n.v += n.lazy;
        add_node(t, n.s, n.e, n.lazy, 2*k);
        add_node(t, n.s, n.e, n.lazy, 2*k+1);
        n.lazy = 0;
    }
    return max(query_node(t, s, e, 2*k), query_node(t, s, e, 2*k+1));
}

int query(tree& t, int s, int e) {
    return query_node(t, s, e, 1);
}

void add(tree& t, int i, int x) {
    add_node(t, i, i, x, 1);
}

void add_range(tree& t, int s, int e, int x) {
    add_node(t, s, e, x, 1);
}

struct task {
    int d, m, i;
};

int main() {
    int T; cin >> T;
    vector<task> ts;
    for (int i = 0; i < T; ++i) {
        task t{0,0,i};
        cin >> t.d >> t.m;
        ts.push_back(t);
    }
    sort(begin(ts), end(ts), [](auto& t1, auto& t2) { return t1.d < t2.d; });
    vector<int> ixs(T);
    for (int i = 0; i < T; ++i) {
        ixs[ts[i].i] = i;
    }
    vector<int> over(T);
    for (int i = 0; i < T; ++i) {
        over[i] = -ts[i].d;
    }
    auto tr = mk_tree(over);
    for (int i = 0; i < T; ++i) {
        auto j = ixs[i];
        auto t = ts[j];
        add_range(tr, j, T-1, t.m);
        cout << max(0, query(tr, 0, T-1)) << endl;
    }
}

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

int main() {
    int H; int W; int K;
    while (~scanf("%d%d%d", &H, &W, &K)) {
        vector<string> maze(H);
        rep(i, H) {
            char buf[101];
            scanf("%s", buf);
            maze[i] = buf;
        }
        vector<int> tunnel(H * W, -1);
        rep(i, K) {
            int y1; int x1; int y2; int x2;
            scanf("%d%d%d%d", &y1, &x1, &y2, &x2), -- y1, -- x1, -- y2, -- x2;
            int u = y1 * W + x1, v = y2 * W + x2;
            tunnel[u] = v;
            tunnel[v] = u;
        }
        vector<vector<pair<int, double>>> gw(H * W);
        rep(i, H) rep(j, W) {
            int u = i * W + j;
            if (!strchr("#*%", maze[i][j])) {
                static const int dy[4] = { 0, 1, 0, -1 }, dx[4] = { 1, 0, -1, 0 };
                for (int d = 0; d < 4; ++ d) {
                    int yy = i + dy[d], xx = j + dx[d];
                    if (yy < 0 || yy >= H || xx < 0 || xx >= W) continue;
                    if (maze[yy][xx] == '#') continue;
                    int v = yy * W + xx;
                    if (tunnel[v] != -1)
                        v = tunnel[v];
                    gw[u].emplace_back(v, 1.);
                }
            }
            if (gw[u].empty()) {
                gw[u].emplace_back(u, 1.);
            } else {
                for(auto &p : gw[u])
                    p.second /= (int)gw[u].size();
            }
        }
        //(1 - A)^{-1} c
        typedef double Num;
        vector<vector<Num>> A(H * W, vector<Num>(H * W)), B = A;
        rep(u, H * W) for (auto e : gw[u])
            A[u][e.first] += e.second;
        rep(iter, 20) {
            rep(i, H * W) rep(j, H * W) {
                Num x = 0;
                rep(k, H * W)
                    x += A[i][k] * A[k][j];
                if (x < 1e-20)
                    x = 0;
                B[i][j] = x;
            }
            A.swap(B);
        }
        double ans = 0;
        rep(i, H) rep(j, W) if (maze[i][j] == 'A')
            rep(k, H) rep(l, W) if(maze[k][l] == '%')
                ans += A[i * W + j][k * W + l];
        printf("%.10f\n", ans);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define IDX 0   
#define COUNT 1  

int MaxNonOverlapSegments(const vector<int>& nums)
{
    int size_ = nums.size();
    if (size_ < 2) return 0;

    int max_count = 1;
    unordered_map<int, vector<int>> sum_;

    for (int i = 0; i + 1 < size_; ++i)
    {
        auto it = sum_.find(nums[i] + nums[i + 1]);

        if (sum_.end() == it)
        {
            sum_.emplace(nums[i] + nums[i + 1], vector<int>{i + 1, 1});
            continue;
        }

        vector<int>& val = it->second;

        if (val[IDX] + 1 > i)
        {
            continue;
        }

        val[IDX] = i + 1;
        ++val[COUNT];

        max_count = max(max_count, val[COUNT]);
    }

    return max_count;
}

#include <iostream>
#include <string>
using namespace std;

string solution(string &S, string &T) {
    int n = S.size();
    int m = T.size();
    if (S == T) {
        return "NOTHING";
    }
    
    if (m == n + 1 && T.substr(0, n) == S) {
        return "ADD " + string(1, T[n]);
    }
    
    if (n == m + 1) {
        for (int i = 0; i < n - 1; i++) {
            if (S[i] == S[i + 1]) {
                string mergedS = S.substr(0, i) + S.substr(i + 1);
                if (mergedS == T) {
                    return "JOIN " + string(1, S[i]);
                }
            }
        }
    }
    
    if (n == m) {
        int first_diff = -1, second_diff = -1;
        
        for (int i = 0; i < n; ++i) {
            if (S[i] != T[i]) {
                if (first_diff == -1) {
                    first_diff = i;
                } else if (second_diff == -1) {
                    second_diff = i;
                } else {
                    return "IMPOSSIBLE";
                }
            }
        }

        if (second_diff != -1 && S[first_diff] == T[second_diff] && S[second_diff] == T[first_diff]) {
            return "SWAP " + string(1, S[first_diff]) + " " + string(1, S[second_diff]);
        }
    }
    
    return "IMPOSSIBLE";
}

import java.util.HashMap;
class Solution {
    public int solution(String S) {
        int maxLength = 0;
        for (int start = 0; start < S.length(); start++) {
            HashMap<Character, Integer> charCount = new HashMap<>();
            
            for (int end = start; end < S.length(); end++) {
                char currentChar = S.charAt(end);
                    charCount.put(currentChar, charCount.getOrDefault(currentChar, 0) + 1);

                if (allEven(charCount)) {
                    maxLength = Math.max(maxLength, end - start + 1);
                }
            }
        }

        return maxLength;
    }
    private boolean allEven(HashMap<Character, Integer> charCount) {
        for (int count : charCount.values()) {
            if (count % 2 != 0) {
                return false;
            }
        }
        return true;
    }

#include <iostream>
using namespace std;
class TreeNode {
public:
    int x; 
    TreeNode* left; 
    TreeNode* right; 

    TreeNode(int value) : x(value), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* solution(TreeNode* T) {
        if (!T) return nullptr; 

        if (!T->left && !T->right) {
            TreeNode* newNode = new TreeNode(T->x);
            newNode->left = new TreeNode(T->x);  
            newNode->right = new TreeNode(T->x); 
            return newNode;
        }

        if (T->left) {
            T->left = solution(T->left);
        }
        if (T->right) {
            T->right = solution(T->right);
        }

        return T;  
    }
};