#P1772. New Go Game

New Go Game

Description

The history of Go traces back to some 3,000 years, and the rules have remained essentially unchanged throughout this very long period. The game probably originated in China or the Himalayas. Mythology says that the future of Tibet was once decided over a Go board, when the Buddhist ruler refused to go into battle; instead he challenged the aggressor to a game of Go to avoid bloodshed.

Like Chess, Go is a game of skill, but it differs from Chess in many ways. The rules of Go are very simple, like Chess, it is a challenge to players' analytical skills, but there is far more scope in Go for intuition.

Go is a territorial game. The board, marked with a grid of 19 lines by 19 lines, may be thought of as a piece of land to be shared between the two players. One player has a supply of black pieces,called stones, the other a supply of white. The game starts with an empty board and the players take turns, placing one stone at each turn on a vacant point. Black plays first, and the stones are placed on the intersections of the lines rather than in the squares.

Now, forget the rules of the original Go game. I'll tell you how to play it with only black stones.Let me put some black stones on an empty board first. Then, you are supposed to tell me how many intersections are enclosed by the black stones. What? You can't tell which intersection is enclosed? OK. I'll make it clear. The first, an enclosed intersection must be an intersection without any stone on it. The second, an intersection at any border can't be an enclosed intersection. The third, the four near intersections (up, down, left, right) must be enclosed intersections or be occupied by a black stone. As the figure below, there are 3 enclosed intersections.

It's very easy. But, hold on please. It shouldn't be so easy. For some reason, you don't know where the black stones have been put directly.

Four groups of numbers are used to describe the situation of an N*N board. In the 1st group, there are N numbers, and the kth number indicates the quantity of black stones on the kth row (from up to down, 1 <= k <= N). In the 2nd group, there are also N numbers, and the kth number in this group indicates the quantity of black stones on the kth column (from left to right, 1 <= k <= N). In the 3rd group, there are 2N-1 numbers, which indicate the quantity of black stones on every slanted line one by one (from left to right, from up to down). In the 4th group, there are also 2N-1 numbers,and they indicate the quantity of black stones on every oblique line one by one (from left to right,from down to up). So, the above 5*5 board with several black stones can be described as below four groups of numbers.

1st group 1 3 2 3 1

2nd group 0 2 2 2 4

3rd group 0 0 1 3 0 2 2 1 1

4th group 0 0 0 2 3 2 1 2 0

Now, your task is to write a program to rebuild the board from the four groups of numbers (I'm sure you can rebuild one and only one board from our numbers), and tell me how many enclosed intersections in it.

Input

The input contains several testcases. The first line of each testcase is an integer N (N <= 15),representing the size of the board. Then, four lines follow, representing the numbers in the 1st group, 2nd group … and so on.

The input is terminated by a single zero.

Output

For each testcase, output an integer indicating the number of intersections that are enclosed by black stones on the board in a single line. No extra spaces are allowed.

5
1 3 2 3 1
0 2 2 2 4
0 0 1 3 0 2 2 1 1
0 0 0 2 3 2 1 2 0
0
3

Source

Asia Guangzhou 2003