// LOTTERY
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;

int dp[1001][1001][26]; // Adjust size as needed based on the problem constraints

int getCharWithDiff(char ch, int diff) {
    int code = ch - 'a';
    return ((code + diff + 26) % 26) + 'a';
}

int dfs(const string &lotteryID, const string &winnerID, int i, int j, int remainingK, int m, int n) {
    if (i == m || j == n) return 0;
    if (remainingK < 0) return 0;
    if (dp[i][j][remainingK] != -1) return dp[i][j][remainingK];

    int result = max(
        dfs(lotteryID, winnerID, i + 1, j, remainingK, m, n),
        dfs(lotteryID, winnerID, i, j + 1, remainingK, m, n)
    );

    if (lotteryID[i] == winnerID[j]) {
        result = max(result, 1 + dfs(lotteryID, winnerID, i + 1, j + 1, remainingK, m, n));
    } else if (remainingK > 0) {
        for (int diff = 1; diff <= min(25, remainingK); ++diff) {
            if (getCharWithDiff(lotteryID[i], diff) == winnerID[j] ||
                getCharWithDiff(lotteryID[i], -diff) == winnerID[j]) {
                result = max(result, 1 + dfs(lotteryID, winnerID, i + 1, j + 1, remainingK - diff, m, n));
                break;
            }
        }
    }

    dp[i][j][remainingK] = result;
    return result;
}

int maxLCSAfterOperations(const string &lotteryID, const string &winnerID, int k) {
    int m = lotteryID.size();
    int n = winnerID.size();
    memset(dp, -1, sizeof(dp));
    return dfs(lotteryID, winnerID, 0, 0, k, m, n);
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;
string findStringFromIcp(vector<vector<int>>& icp) {
    int n = icp.size();
        for (int i = 0; i < n; i++) {
        if (icp[i][i] != n - i) { 
            return "Impossible";
        }
        for (int j = i + 1; j < n; j++) {
            if (icp[i][j] != icp[j][i]) {  
                return "Impossible";
            }
        }
    }
        string result(n, ' '); 
    result[0] = 'a';       
    for (int i = 1; i < n; i++) {
        bool assigned = false;
        for (int j = 0; j < i; j++) {
            if (icp[j][i] > 0) {
                result[i] = result[j]; 
                assigned = true;
                break;
            }
        }
        if (!assigned) {
            result[i] = result[i - 1] + 1; 
            if (result[i] > 'z') {
                return "Impossible";  
            }
        }
    }
        for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int commonLength = 0;
            while (i + commonLength < n && j + commonLength < n && result[i + commonLength] == result[j + commonLength]) {
                commonLength++;
            }
            if (commonLength != icp[i][j]) {
                return "Impossible";
            }
        }
    }
    
    return result; 
}

struct Cell { 
    int x, y, cost; 
}; 

int minimumEnergy(vector<string> river, int initial_x, int initial_y, int final_x, int final_y) { 
    int rows = river.size(); 
    int cols = river[0].size(); 

    vector<vector<bool>> visited(rows, vector<bool>(cols, false)); 
    queue<Cell> q; 
    int dx[] = {-1, 1, 0, 0}; 
    int dy[] = {0, 0, -1, 1}; 

    q.push({initial_x, initial_y, 0}); 
    visited[initial_x][initial_y] = true; 

    while (!q.empty()) { 
        Cell current = q.front(); 
        q.pop(); 

        if (current.x == final_x && current.y == final_y) { 
            return current.cost; 
        } 

        for (int i = 0; i < 4; i++) { 
            int next_x = current.x + dx[i]; 
            int next_y = current.y + dy[i]; 

            if (next_x >= 0 && next_x < rows && next_y >= 0 && next_y < cols && 
                river[next_x][next_y] != '#' && !visited[next_x][next_y]) { 

                visited[next_x][next_y] = true; 

                int updatedCost = current.cost; 

                if ((dx[i] == -1 && dy[i] == 0) || (dx[i] == 0 && dy[i] == -1)) { 
                    updatedCost += 1;  
                } 

                q.push({next_x, next_y, updatedCost}); 
            } 
        } 
    } 

    return -1;  
}

import java.util.*;
public class Main {
    static int countMatches(List<String> grid1, List<String> grid2) {
        int count = 0;
        int m = grid1.size();
        int n = grid1.get(0).length();
        int[][] g1 = new int[m][n];
        int[][] g2 = new int[m][n];
        int[][] orMap = new int[m][n];
        for(int i=0; i<m; i++){
            char[] str1 = grid1.get(i).toCharArray();
            char[] str2 = grid2.get(i).toCharArray();
            for(int j=0; j<n; j++){
                g1[i][j] = str1[j] - '0';
                g2[i][j] = str2[j] - '0';
            }
        }
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                orMap[i][j] = g1[i][j] | g2[i][j];
            }
        }
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(orMap[i][j] == 1 && dfs(g1, g2, orMap, i, j)) count++;
            }
        }
        return count;
    }

    private static boolean dfs(int[][] g1, int[][] g2, int[][] orMap, int i, int j) {
        int m = orMap.length;
        int n = orMap[0].length;
        orMap[i][j] = 0;
        boolean up = true, down = true, left = true, right = true;
        if(i > 0 && orMap[i-1][j] == 1) up = dfs(g1, g2, orMap, i-1, j);
        if(i < m - 1 && orMap[i+1][j] == 1) down = dfs(g1, g2, orMap, i+1, j);
        if(j > 0 && orMap[i][j-1] == 1) left = dfs(g1, g2, orMap, i, j-1);
        if(j < n - 1 && orMap[i][j+1] == 1) right = dfs(g1, g2, orMap, i, j+1);

        return g1[i][j] == 1 && g2[i][j] == 1 && up && down && left && right;
    }