9115: Puzzle: Arithmetic Square

题目描述

Grammy is a puzzle master. Today, she is playing a variant of "Arithmetic Square" puzzle.

The puzzle consists of a $(2n-1)\times (2m-1)$ grid. The intersection of odd rows and odd columns are empty and needed to be filled in with pairwise distinct integers. The intersection of even rows and even columns are blocked. All other cells consists of either "$\text{+}$" or "$\text{-}$".

Each odd row and odd column forms an expression in the grid. The expressions should evaluate to the clues given in the right of the grid and in the bottom of the grid. The goal is to fill in all the empty squares with pairwise distinct integers so that all of the expressions are satisfied.



The left picture illustrates a $5\times 5$ empty puzzle, and the right picture shows a solution to the puzzle.

Grammy surely knows how to solve the puzzle, but she decided to give you a quiz. Please solve the puzzle.

The first line contains two integers $n,m$ ($2\le n,m\le 1000$), denoting the size of the grid. 

The following $2n-1$ lines contains $2m-1$ characters each, denoting the symbols in the grid. "$\text{.}$" denotes an empty cell, "" denotes a blocked cell, "$\text{+}$" denotes a plus sign, and "$\text{-}$" denotes a minus sign. 
The next line contains $n$ integers rir_iri (−109≤ri≤109-10^9 \leq r_i \leq 10^9−109≤ri≤109), denoting the clues for each row on the right of the grid. 
The next line contains $m$ integers cic_ici (−109≤ci≤109-10^9 \leq c_i \leq 10^9−109≤ci≤109), denoting the clues for each column on the bottom of the grid.