Bob is composing a song for singers to perform! The song lasts for
beats, and the
-th singer is assigned a series of
notes
to sing on each of the beats. Notes are represented by integer values, and the
notes sung on a single beat are all distinct.
Unfortunately, Bob needs to watch out for parallel-s. A parallel-
is a triple
such that
. In other words, a parallel-
is two singers
and
, plus a beat
, such that the notes that
and
sing form an interval of
on both beats
and
.
Parallel-s make music sound absolutely horrendous (for some reason), so please help Bob find all the parallel-
s in his song!
Constraints
For a given ,
are distinct.
Subtask 1 [2/15]
Subtask 2 [5/15]
Subtask 3 [8/15]
Input Specification
The first line contains three space-separated integers: ,
, and
.
The next lines each contain
space-separated integers,
, the notes sung on each beat by singer
.
Output Specification
The number of distinct parallel-s in Bob's song. (Two parallel-
s
and
are distinct if
, or
, or
.)
Sample Input
5 3 5
5 6 6
10 11 11
15 16 16
105 116 118
110 111 113
Sample Output
5
Explanation for Sample Output
Singers 1 and 2 form two parallel-5s: one between beats 1 and 2, and another between beats 2 and 3. Singers 2 and 3 also form two parallel-5s. Finally, singers 5 and 4 form one parallel-5 between beats 2 and 3. In total, there are five parallel-5s: ,
,
,
, and
. (Note that
,
, and
do not fit the definition of a parallel-5.)
Comments