410665: GYM104072 C Battleships

After getting sick of being defeated in Battleships by his friend, Johnny invites him to play a new game of his own design - Mega Battleships. Mega Battleships plays exactly like Battleships, but the board is a lot bigger. The board in this game is $$$10^{6}$$$ by $$$10^{6}$$$.

Because the board is so big, he needs a little help to keep track of what is going on. Given the layout of his boats and the shots his opponent took, can you output the number of boats that were sunk? As a reminder, a boat is considered sunk, if all its cells have been hit.

The first line of the input consists of $$$K$$$ ($$$1 \leq K \leq 10^{6}$$$) pairs of coordinates for the battleships, $$$c_1k$$$ and $$$c_2k$$$, representing the top left corner and bottom right corner respectively. Each pair is separated by a comma. We guarantee that the ships do not overlap.

The second line of the input is the list of distinct coordinates of the shots that were performed by the second player. There are at most $$$10^{6}$$$ such coordinates. They are separated by commas.

All the coordinates are provided in row-column order, with numbers for rows and letters for columns. For example, the top left corner's coordinate is 1A, the cell to its right is 1B, and the cell underneath it is 2A. Generally, the structure of a coordinate $$$c_k$$$ is $$$n_k l_k$$$ where $$$1 \leq n_k \leq 10^{6}$$$ and $$$A \leq l_k \leq BDWGN$$$ (after Z, the next column is AA and so on (and after ZZ, AAA); BDWGN is equivalent to $$$10^{6}$$$).

The output file should consist of one integer which represents the number of ships that were sunk.

1A 2B,3C 3C,1C 2C
1C,2C,3C

2