삼중항

시간 제한2초메모리 제한1024 MB

요약

세 직사각형에서 격자점 쌍 세 개씩을 뽑아 중복된 쌍을 버리고 반대 순서를 상쇄한 뒤 남는 서로 다른 트리플 수를 셉니다.

난이도: 어려움10점 중 8점
유형: 조합론, 수학
정답자: 아직 제출이 없습니다

문제

순서쌍 세 개를 차례로 늘어놓은 것을 삼중항이라 하고 $\langle (a,b), (c,d), (e,f) \rangle$ 로 쓴다.

규칙 1. 세 순서쌍 가운데 두 개가 서로 같으면 그 삼중항은 $0$ 이다.

\begin{aligned} \langle (a,b), (a,b), (a,b) \rangle &= 0 \\ \langle (a,b), (a,b), (e,f) \rangle &= 0 \\ \langle (a,b), (c,d), (a,b) \rangle &= 0 \\ \langle (a,b), (c,d), (c,d) \rangle &= 0 \end{aligned}

값이 $0$ 인 삼중항을 영 삼중항이라 한다.

규칙 2. 이웃한 두 순서쌍을 맞바꾸면 삼중항의 부호가 바뀐다. 홀수 번 맞바꿔서 얻은 삼중항은 원래 삼중항에 $-1$ 을 곱한 것과 같고, 짝수 번 맞바꿔서 얻은 삼중항은 원래 삼중항과 같다. $\langle (1,2), (3,4), (5,6) \rangle$ 에서 이웃한 순서쌍을 하나씩 맞바꾸면

\begin{aligned} \langle (1,2), (3,4), (5,6) \rangle &\to \langle (3,4), (1,2), (5,6) \rangle \\ &\to \langle (3,4), (5,6), (1,2) \rangle \\ &\to \langle (5,6), (3,4), (1,2) \rangle \\ &\to \langle (5,6), (1,2), (3,4) \rangle \\ &\to \langle (1,2), (5,6), (3,4) \rangle \end{aligned}

이 되므로 다음 등식이 성립한다.

\begin{aligned} \langle (1,2), (3,4), (5,6) \rangle &= -\langle (3,4), (1,2), (5,6) \rangle \\ &= \langle (3,4), (5,6), (1,2) \rangle \\ &= -\langle (5,6), (3,4), (1,2) \rangle \\ &= \langle (5,6), (1,2), (3,4) \rangle \\ &= -\langle (1,2), (5,6), (3,4) \rangle \end{aligned}

여섯 정수가

\begin{gathered} a_1 \le a \le a_2, \quad b_1 \le b \le b_2 \\ c_1 \le c \le c_2, \quad d_1 \le d \le d_2 \\ e_1 \le e \le e_2, \quad f_1 \le f \le f_2 \end{gathered}

를 만족하는 삼중항 $\langle (a,b), (c,d), (e,f) \rangle$ 을 모두 더한다. 규칙 1로 영 삼중항을 버리고 규칙 2로 부호만 다른 삼중항끼리 상쇄한 다음, 합에 남은 서로 다른 영이 아닌 삼중항이 몇 개인지 구하는 프로그램을 작성하시오. 규칙 2로 서로 같아지는 삼중항은 같은 삼중항이므로, 같은 부호로 두 번 남아도 하나로 센다.

$a$ , $b$ , $c$ , $d$ , $e$ , $f$ 는 모두 $0$ 이상 $100$ 이하의 정수이고, 답은 $0$ 이상 $1000$ 이하이다.

입력

정수 $12$ 개가 공백 하나로 구분되어 한 줄에 주어진다. 순서는 다음과 같다.

a_1 \quad a_2 \quad b_1 \quad b_2 \quad c_1 \quad c_2 \quad d_1 \quad d_2 \quad e_1 \quad e_2 \quad f_1 \quad f_2

각 범위는 $0 \le a_1 \le a_2 \le 100$ 을 만족하고, 나머지 다섯 범위도 마찬가지다.

출력

합에 남은 서로 다른 영이 아닌 삼중항의 개수를 정수 하나로 출력한다.

예제3

예제 1
입력
```
1 1 2 2 3 3 4 4 5 5 6 8
```
예상 출력
```
3
```
예제 2
입력
```
1 1 2 2 4 5 7 8 5 5 6 8
```
예상 출력
```
8
```
예제 3
입력
```
0 0 0 0 0 0 0 1 0 1 0 1
```
예상 출력
```
2
```