// === ORIGINAL VERSION ===
function THEJOB(input) {
    let n = 0;
    const grid = input.split("\n").map(x => x.split(""));
    const size = [grid.length, grid[0].length];
    let marks = [];
    for(let y = 0; y < size[0]; y++) {
        for(let x = 0; x < size[1]; x++) {
            CHECK(y, x);
        }
    }
    while(marks.length) {
        const length = marks.length;
        for(let m = 0; m < length; m++) {
            const mark = marks[m];
            const y = mark >> 8;
            const x = mark & 255;
            CHECK(y-1, x-1);
            CHECK(y-1, x);
            CHECK(y-1, x+1);
            CHECK(y, x-1);
            CHECK(y, x+1);
            CHECK(y+1, x-1);
            CHECK(y+1, x);
            CHECK(y+1, x+1);
        }
        marks = marks.slice(length);
    }
    function CHECK(y, x) {
        const gy = grid[y];
        if(gy) {
            const gx = gy[x];
            if(gx === "@") {
                let brazil = 0;
                const gyminus = grid[y-1];
                const gyplus = grid[y+1];
                if(gy[x-1] === "@") {brazil++}
                if(gy[x+1] === "@") {brazil++}
                if(gyminus) {
                    if(gyminus[x-1] === "@") {brazil++}
                    if(gyminus[x] === "@") {brazil++}
                    if(gyminus[x+1] === "@") {brazil++}
                }
                if(gyplus) {
                    if(gyplus[x-1] === "@") {brazil++}
                    if(gyplus[x] === "@") {brazil++}
                    if(gyplus[x+1] === "@") {brazil++}
                }
                if(brazil < 4) {
                    n++;
                    gy[x] = ".";
                    marks.push((y << 8) + x);
                }
            }
        }
    }
    return n;
}

// === ULTRA FAST VERSION ===
function THEJOB_ULTRA(input) {
    const lines = input.split("\n");
    const rows = lines.length;
    const cols = lines[0].length;
    const total = rows * cols;
    
    // Flat typed arrays - MUCH faster than 2D arrays
    const grid = new Uint8Array(total);        // 1 = @, 0 = .
    const neighbors = new Uint8Array(total);   // neighbor count
    const inQueue = new Uint8Array(total);     // already queued?
    
    // Double-buffer queues (avoid .slice() allocation)
    const queueA = new Uint32Array(total);
    const queueB = new Uint32Array(total);
    let queue = queueA;
    let nextQueue = queueB;
    let qLen = 0;
    
    // Parse input + build neighbor counts in ONE pass
    for (let y = 0; y < rows; y++) {
        const line = lines[y];
        const rowBase = y * cols;
        
        for (let x = 0; x < cols; x++) {
            if (line.charCodeAt(x) === 64) { // '@' = ASCII 64
                const idx = rowBase + x;
                grid[idx] = 1;
                
                // Increment neighbor count for all 8 neighbors
                const yMin = y > 0 ? -1 : 0;
                const yMax = y < rows - 1 ? 1 : 0;
                const xMin = x > 0 ? -1 : 0;
                const xMax = x < cols - 1 ? 1 : 0;
                
                for (let dy = yMin; dy <= yMax; dy++) {
                    const nRowBase = (y + dy) * cols;
                    for (let dx = xMin; dx <= xMax; dx++) {
                        if (dy | dx) { // skip (0,0)
                            neighbors[nRowBase + x + dx]++;
                        }
                    }
                }
            }
        }
    }
    
    // Find initial candidates with < 4 neighbors
    for (let i = 0; i < total; i++) {
        if (grid[i] && neighbors[i] < 4) {
            queue[qLen++] = i;
            inQueue[i] = 1;
        }
    }
    
    let removed = 0;
    
    // BFS removal
    while (qLen > 0) {
        let nextLen = 0;
        
        for (let i = 0; i < qLen; i++) {
            const idx = queue[i];
            
            // Remove this cell
            grid[idx] = 0;
            removed++;
            
            // Calculate y, x from flat index
            const y = (idx / cols) | 0;
            const x = idx - y * cols;
            
            // Update neighbors and queue new candidates
            const yMin = y > 0 ? -1 : 0;
            const yMax = y < rows - 1 ? 1 : 0;
            const xMin = x > 0 ? -1 : 0;
            const xMax = x < cols - 1 ? 1 : 0;
            
            for (let dy = yMin; dy <= yMax; dy++) {
                const nRowBase = (y + dy) * cols;
                for (let dx = xMin; dx <= xMax; dx++) {
                    if (dy | dx) {
                        const nIdx = nRowBase + x + dx;
                        const newCount = --neighbors[nIdx];
                        
                        if (newCount < 4 && grid[nIdx] && !inQueue[nIdx]) {
                            inQueue[nIdx] = 1;
                            nextQueue[nextLen++] = nIdx;
                        }
                    }
                }
            }
        }
        
        // Swap buffers (zero allocation!)
        const tmp = queue;
        queue = nextQueue;
        nextQueue = tmp;
        qLen = nextLen;
    }
    
    return removed;
}

// === BENCHMARK ===
function generateGrid(rows, cols, density = 0.7) {
    let result = '';
    for (let y = 0; y < rows; y++) {
        let row = '';
        for (let x = 0; x < cols; x++) {
            row += Math.random() < density ? '@' : '.';
        }
        result += row + (y < rows - 1 ? '\n' : '');
    }
    return result;
}

function benchmark(fn, input, name, iterations = 5) {
    // Warmup
    fn(input);
    fn(input);
    
    let total = 0;
    let result;
    for (let i = 0; i < iterations; i++) {
        const start = performance.now();
        result = fn(input);
        total += performance.now() - start;
    }
    
    return { 
        name, 
        avgTime: total / iterations, 
        result 
    };
}

console.log('🔥 BENCHMARK: ORIGINAL vs ULTRA 🔥\n');
console.log('=' .repeat(60));

const tests = [
    { rows: 50, cols: 50, name: "50x50" },
    { rows: 100, cols: 100, name: "100x100" },
    { rows: 200, cols: 200, name: "200x200" },
    { rows: 500, cols: 500, name: "500x500" },
    { rows: 1000, cols: 1000, name: "1000x1000" },
];

for (const test of tests) {
    console.log(`\n📊 Grid: ${test.name} (${(test.rows * test.cols).toLocaleString()} cells)`);
    console.log('-'.repeat(50));
    
    const input = generateGrid(test.rows, test.cols);
    
    // Skip original for very large grids (too slow)
    let origResult = null;
    let origTime = null;
    
    if (test.rows <= 200) {
        const orig = benchmark(THEJOB, input, "ORIGINAL", 3);
        origResult = orig.result;
        origTime = orig.avgTime;
        console.log(`  ORIGINAL:  ${origTime.toFixed(2)} ms  (result: ${origResult})`);
    } else {
        console.log(`  ORIGINAL:  SKIPPED (too slow)`);
    }
    
    const ultra = benchmark(THEJOB_ULTRA, input, "ULTRA", 5);
    console.log(`  ULTRA:     ${ultra.avgTime.toFixed(2)} ms  (result: ${ultra.result})`);
    
    if (origTime !== null) {
        const speedup = origTime / ultra.avgTime;
        console.log(`  ⚡ SPEEDUP: ${speedup.toFixed(1)}x faster`);
        console.log(`  ✓ Results match: ${origResult === ultra.result ? 'YES ✅' : 'NO ❌'}`);
    }
    
    const cellsPerMs = (test.rows * test.cols) / ultra.avgTime;
    console.log(`  📈 Throughput: ${(cellsPerMs / 1000).toFixed(1)}M cells/sec`);
}

console.log('\n' + '='.repeat(60));
console.log('🏁 BENCHMARK COMPLETE');

// Verification tests
console.log('\n\n🧪 VERIFICATION TESTS:\n');

const verifyTests = [
    { name: "5x5 full", input: "@@@@@\n@@@@@\n@@@@@\n@@@@@\n@@@@@" },
    { name: "Single @", input: "@" },
    { name: "Line", input: "@@@@@" },
    { name: "Checkerboard", input: "@.@.@\n.@.@.\n@.@.@\n.@.@.\n@.@.@" },
];

for (const t of verifyTests) {
    const orig = THEJOB(t.input);
    const ultra = THEJOB_ULTRA(t.input);
    const match = orig === ultra ? '✅' : '❌';
    console.log(`  ${t.name}: ORIG=${orig} ULTRA=${ultra} ${match}`);
}