## DMOPC '20 Contest 3 P2 - Bob and Parallel-Ks

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

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.

#### 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.)