#216182. [ICPC 2019 NAIPC] Monotony

You are given an grid. Each cell of this grid is filled with a number between and inclusive, and each cell’s number is distinct.

Define a grid of numbers to be monotonic if each row and column is either increasing or decreasing (this can be different for each row or column).

Define a subgrid of the grid as follows: First choose some nonempty subset of the rows and columns. Next, take elements that lie in both the chosen rows and columns in the same order.

There are nonempty subgrids of the given grid. Of these subgrids, count how many are monotonic.

Consider this grid:

There are nine subgrids, nine ’s, three ’s, nine ’s, nine ’s, three ’s, three ’s, three ’s, and one . They are all monotonic, for monotonic subgrids.

Each test case will begin with a line with two space-separated integers and (), which are the dimensions of the grid.

Each of the next lines will contain space-separated integers (, all ’s are unique). This is the grid.

Output a single integer, which is the number of monotonic subgrids in the given grid.

样例输入 1

3 3
1 2 5
7 6 4
9 8 3

样例输出 1

49

样例输入 2

4 3
8 2 5
12 9 6
3 1 10
11 7 4

样例输出 2

64