Cards Domination

Alice and Bob are playing a card game. Every card has four attributes: Attack, Defense, Speed, and Health. We say that a card \( X = (x_1,x_2,x_3,x_4) \) beats another card \( Y = (y_1,y_2,y_3,y_4) \) if and only if at least three out of the four attributes of \( X \) are strictly greater than the corresponding attributes of \( Y \); that is, \( |\{ i \mid x_i>y_i \}|\ge3 \).

Bob owns \( m \) cards. Alice, on the other hand, owns every card whose attributes are integers in the range \([1,n]\). Hence, Alice has a total of \( n^4 \) different cards available.

Alice is wondering: how many of her cards can beat every one of Bob's cards? In other words, count the number of quadruples \( (x_1,x_2,x_3,x_4) \) with \( 1\le x_i\le n \) such that for every Bob's card \( b=(b_1,b_2,b_3,b_4) \), it holds that \( |\{ i \mid x_i>b_i \}|\ge3 \).

Hint: Let \( T=(T_1,T_2,T_3,T_4) \) where \( T_i=\max\{b_i \mid b \text{ is one of Bob's cards}\} \). A necessary and sufficient condition for an Alice card \( X=(x_1,x_2,x_3,x_4) \) to beat all Bob's cards is that it beats the card \( T \) in at least three attributes. That is, either:

• \( x_i>T_i \) for all \( i \) (all four attributes are greater), or
• There exists exactly one index \( k \) such that \( x_k\le T_k \) and \( x_j>T_j \) for all \( j\neq k \).

Therefore, the answer can be computed as:

[ \text{answer} = \prod_{i=1}^{4}(n-T_i) + \sum_{k=1}^{4}\left(T_k \prod_{\substack{j=1\ j\neq k}}^{4}(n-T_j)\right). ]

inputFormat

The first line contains two integers \( n \) and \( m \) (\( 1 \le n \le 10^9 \); \( 1 \le m \le 10^5 \)). Each of the following \( m \) lines contains four integers, representing the attributes of one of Bob's cards. All attributes are in the range \([1,n]\).

outputFormat

Output a single integer, the number of cards from Alice's collection that can beat every one of Bob's cards according to the rule defined.

sample

10 1
2 3 4 5

5620