Let F : $\{0,1\}$k $\backslash$times $\{0,1\}$n $->\{0,1\}$n be a good MAC. Suppose that a database contains records M$1,...,$ Mq $.$ To provide authenticity for the records, the admin generates a random secret key K in $\{0,1\}$k and stores Ti $$ FK$($Mi$)$ alongside record Mi for every i $=1,...,$ q$.$ This does not ensure authenticity because an attacker can remove a record or duplicate a record without being detected. To deal with this, the admin generates another secret key K$$ in $\{0,1\}$k and computes an additional tag T $.$ She stores $($K$,$ K$,$ T $)$ in her machine, away from the database.

How should the admin compute T$$ so that if we update a single record Mi$,$ the cost to update $($Ti$,$T$)$ is cheap, meaning we need to run the MAC to sign messages of total size O$(|$Mi$|+$qn$)?$ Briefly explain why your solution can detect if an adversary modified the database.