Sleeping schedule

Darío has a weird sleeping schedule. And I mean really weird. It has gotten so bad that, whenever the National Cybersecurity Agency needs a pseudorandom number for encrypting purposes, they simply call Darío and ask him what time he woke up that morning.

The constant calls are beginning to annoy Darío (how is he supposed to think about math with all these interruptions?), so he has decided he is going to standardize his routine. However, he wants his schedule to satisfy a few restrictions.

To begin with, Darío’s days have $h$ hours, instead of the usual $24$ , which he numbers from $0$ to $h-1$ . He will choose:

a fixed time $w$ at which to wake up, and
a fixed time $s$ at which to go to sleep.

Every day, he will sleep from $w$ to $s$ . In particular, if both times are equal, he will sleep for 0 hours. For example, if $h = 10$ , going to sleep at 7:00 and getting up at 2:00 means that Darío will sleep for 5 hours.

His chosen times must also satisfy the following conditions:

Both times must be multiples of an hour (e.g. he can go to sleep at 9:00 or 4:00 but not at 4:23).
He must wake up at a time when the dining hall is open (as everyone knows, a good day starts with a good breakfast).
He must go to sleep at a time when there is no ICPC training (otherwise, he would never stick to his schedule).

Darío has given you a list with the $n$ hours in which there is no ICPC training, and the $m$ hours in which the dining hall is open. He will choose uniformly at random both $w$ and $s$ (one independently from the other). Can you compute the average number of hours he will be sleeping per day?

Input

Input consists of multiple cases, only with integer numbers. Each case begins with $h$ , $n$ and $m$ , all between 1 and $10^5$ . Follow $n$ distinct integers $a_1, \dots, a_n$ satisfying $0 \le a_i < h$ , indicating the hours with no ICPC training. Follow $m$ distinct integers $b_1, \dots, b_m$ satisfying $0 \le b_i < h$ , indicating the hours with the dining hall open.

Output

For each case, print with 4 digits after the decimal point the expected number of hours that Darío will be sleeping. The given input cases will have no precission issues.

Problem information

Author: Xavier Povill
Event: Vint-i-quatrè Concurs de Programació de la UPC - Semifinal
Date: 2026-06-18

Generation: 2026-06-12T10:13:48.858Z