Problem H
Daring Doubt

There are two sides to every story.

Figure 1: Illustration by Kyle Coate.

Last year, you heard Daring Do’s. But what about Dr. Caballeron’s?

Daring Do and Dr. Caballeron had both raced to Tenochtitlan, originally seeking to acquire the Truth Talisman of Tonatiuh for their own reasons. The mysterious artifact was not unprotected, however: soon after it was disturbed, the vicious guardian-goyles and the temple’s protector—Ahuizotl—were awoken, and arrived to destroy them.

After a long and protracted struggle, Daring Do and Dr. Caballeron found themselves trapped in a narrow passage, the walls around them quickly crumbling. Fearing that this may be their end, they decided to tie up loose ends; compelled to tell the truth by the power of the Truth Talisman of Tonatiuh, they told each other their side of the story...

Daring Do recollects $D$ events in her story, while Dr. Caballeron recollects $C$ events in his. No event is recollected more than once by Daring Do, and no event is recollected more than once by Dr. Caballeron. There are, however, some events which are recollected by both of them; in total, there are exactly $M$ distinct events between them, labeled $1$ to $M$.

The $i^\text {th}$ event Daring Do recollected is $A_ i$, and the $i^\text {th}$ event Dr. Caballeron recollected is $B_ i$.

Define an experience as a non-empty subset of the $M$ events.

An experience appears in a story if the corresponding subset of events appears, in some order, as consecutive events recollected in that story. More formally, if the events $e_1, e_2, \dots , e_ n$ were recollected in this order in a story $t$, then an experience $s \subseteq \{ 1, 2, \dots , M\} $ appears in $t$ if and only if there exist some $i, j$ with $1 \leq i \leq j \leq n$ such that $\{ e_ i, e_{i+1}, \dots , e_ j\} = s$.

An experience is mutual if it appears in both Daring Do’s and Dr. Caballeron’s stories.

Perhaps, once they learn just how many mutual experiences they share, they will realize that a lot of their conflicts arose from mere misunderstandings. There isn’t much time left, but maybe you can help them make amends?

Input

The first line of input contains three integers, $D$, $C$ ($1 \leq D, C \leq 300\, 000$) and $M$ ($\max (D, C) \leq M \leq D+C$), the number of events in Daring Do’s story, the number of events in Dr. Caballeron’s story and the total number of distinct events, respectively.

The second line of input contains $D$ integers $A_1, A_2, \dots , A_ D$ ($1 \leq A_ i \leq M$), denoting the labels of the events Daring Do recollected in her story.

The third line of input contains $C$ integers $B_1, B_2, \dots , B_ C$ ($1 \leq B_ i \leq M$), denoting the labels of the events Dr. Caballeron recollected in his story.

It is guaranteed that there are no events recollected more than once by Daring Do or Dr. Caballeron, and for all positive integers $k \leq M$, either there exists some $i$ such that $A_ i = k$ or there exists some $i$ such that $B_ i = k$ (or both).

Output

Output the a single integer on a line by itself, the number of mutual experiences.

6 7 8
1 2 5 3 6 8
4 5 1 2 7 6 3

8

8 8 16
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16

0