






from __future__ import annotations





def    __lowerCAmelCase   (    __snake_case							):

     # preprocessing the first row
     for i in range(1       ,			len(matrix[0]							)							):
          matrix[0][i] += matrix[0][i - 1]

     # preprocessing the first column
     for i in range(1       ,			len(__snake_case							)							):
          matrix[i][0] += matrix[i - 1][0]

     # updating the path cost for current position
     for i in range(1       ,			len(__snake_case							)							):
          for j in range(1       ,			len(matrix[0]							)							):
               matrix[i][j] += min(matrix[i - 1][j]       ,			matrix[i][j - 1]							)

     return matrix[-1][-1]


if __name__ == "__main__":
 import doctest

 doctest.testmod()














import itertools
import string
from collections.abc import Generator, Iterable





def    __lowerCAmelCase   (    __snake_case       ,			__snake_case							):
     __lowerCAmelCase             =       iter(__snake_case							)
     while True:
          __lowerCAmelCase             =       tuple(itertools.islice(__snake_case       ,			__snake_case							)							)
          if not chunk:
               return
          yield chunk





def    __lowerCAmelCase   (    __snake_case							):
     __lowerCAmelCase             =       "".join([c.upper() for c in dirty if c in string.ascii_letters]							)
     __lowerCAmelCase             =       ""

     if len(__snake_case							) < 2:
          return dirty

     for i in range(len(__snake_case							) - 1							):
          clean += dirty[i]

          if dirty[i] == dirty[i + 1]:
               clean += "X"

     clean += dirty[-1]

     if len(__snake_case							) & 1:
          clean += "X"

     return clean





def    __lowerCAmelCase   (    __snake_case							):
     # I and J are used interchangeably to allow
     # us to use a 5x5 table (25 letters)
     __lowerCAmelCase             =       "ABCDEFGHIKLMNOPQRSTUVWXYZ"
     # we're using a list instead of a '2d' array because it makes the math
     # for setting up the table and doing the actual encoding/decoding simpler
     __lowerCAmelCase             =       []

     # copy key chars into the table if they are in `alphabet` ignoring duplicates
     for char in key.upper():
          if char not in table and char in alphabet:
               table.append(__snake_case							)

    # fill the rest of the table in with the remaining alphabet chars
     for char in alphabet:
          if char not in table:
               table.append(__snake_case							)

     return table





def    __lowerCAmelCase   (    __snake_case       ,			__snake_case							):
     __lowerCAmelCase             =       generate_table(__snake_case							)
     __lowerCAmelCase             =       prepare_input(__snake_case							)
     __lowerCAmelCase             =       ""

     # https://en.wikipedia.org/wiki/Playfair_cipher#Description
     for chara, chara in chunker(__snake_case       ,			2							):
          __lowerCAmelCase      ,			__lowerCAmelCase             =       divmod(table.index(__snake_case							)       ,			5							)
          __lowerCAmelCase      ,			__lowerCAmelCase             =       divmod(table.index(__snake_case							)       ,			5							)

          if rowa == rowa:
               ciphertext += table[rowa * 5 + (cola + 1) % 5]
               ciphertext += table[rowa * 5 + (cola + 1) % 5]
          elif cola == cola:
               ciphertext += table[((rowa + 1) % 5) * 5 + cola]
               ciphertext += table[((rowa + 1) % 5) * 5 + cola]
          else:  # rectangle
               ciphertext += table[rowa * 5 + cola]
               ciphertext += table[rowa * 5 + cola]

     return ciphertext





def    __lowerCAmelCase   (    __snake_case       ,			__snake_case							):
     __lowerCAmelCase             =       generate_table(__snake_case							)
     __lowerCAmelCase             =       ""

     # https://en.wikipedia.org/wiki/Playfair_cipher#Description
     for chara, chara in chunker(__snake_case       ,			2							):
          __lowerCAmelCase      ,			__lowerCAmelCase             =       divmod(table.index(__snake_case							)       ,			5							)
          __lowerCAmelCase      ,			__lowerCAmelCase             =       divmod(table.index(__snake_case							)       ,			5							)

          if rowa == rowa:
               plaintext += table[rowa * 5 + (cola - 1) % 5]
               plaintext += table[rowa * 5 + (cola - 1) % 5]
          elif cola == cola:
               plaintext += table[((rowa - 1) % 5) * 5 + cola]
               plaintext += table[((rowa - 1) % 5) * 5 + cola]
          else:  # rectangle
               plaintext += table[rowa * 5 + cola]
               plaintext += table[rowa * 5 + cola]

     return plaintext






