class TopKStocksMovingWindow 
{
    struct Trade {
        string symbol;
        int volume;
        long long timestamp;
    };        

    int                                 windowSizeSeconds;
    deque<Trade>                        tradesDQ;
    unordered_map<string, int>          symbolToVolumeMap;
    // pair< volume,symbol >
    //       ------ ------   sorting
    set<pair<int,   string>, greater<>> sortedVolumeSet;


public:
    MovingWindowTicker(int seconds) : windowSizeSeconds(seconds) {}

    void addTrade(string symbol, int volume, long long timestamp) {
        removeOutOfWindowTrade(timestamp);

        // Remove from set to update volume
        if (symbolToVolumeMap.count(symbol)) {
            sortedVolumeSet.erase({symbolToVolumeMap[symbol], symbol});
        }

        symbolToVolumeMap[symbol] += volume;
        tradesDQ.push_back({symbol, volume, timestamp});
        
        // Re-insert updated volume
        sortedVolumeSet.insert({symbolToVolumeMap[symbol], symbol});
    }

    vector<string> getTopK(int k, long long currentTime) {
        removeOutOfWindowTrade(currentTime);
        
        vector<string> result;
        auto it = sortedVolumeSet.begin();
        for (int i = 0; i < k && it != sortedVolumeSet.end(); ++i, ++it) {
            result.push_back(it->second);
        }
        return result;
    }

    // Removes trades that are older than (currentTime - windowSizeSeconds)
    void removeOutOfWindowTrade(long long currentTime) {
        while (!tradesDQ.empty() && tradesDQ.front().timestamp <= currentTime - windowSizeSeconds) {
            Trade expired = tradesDQ.front();
            tradesDQ.pop_front();

            // 1. Remove old entry from set
            sortedVolumeSet.erase({symbolToVolumeMap[expired.symbol], expired.symbol});

            // 2. Subtract volume
            symbolToVolumeMap[expired.symbol] -= expired.volume;

            // 3. Re-insert if volume is still > 0, otherwise clear map of zero
            //      volume symbol
            if (symbolToVolumeMap[expired.symbol] > 0) {
                sortedVolumeSet.insert({symbolToVolumeMap[expired.symbol], expired.symbol});
            } else {
                symbolToVolumeMap.erase(expired.symbol);
            }
        }
    }    
};