#!/bin/bash
INF=100000000000
NINF=-$INF
rm -rf /tmp/abc119d 2> /dev/null
mkdir -p /tmp/abc119d/repo
cd /tmp/abc119d/repo || exit

exec 3>&1 1> /dev/null 2> /dev/null

git init .
git config user.name 'a'
git config user.email 'a'
echo "AtCoder Beginner Contest 119 -- D - Lazy Faith" > README
git add -A
git commit -m "Add README"
git tag initial

echo $NINF > val
git add -A
git commit -m "s-1::$NINF"
git checkout -b shrines
git tag shrines-initial

function distance() {
    da=$(($2 - $1))
    db=$(($3 - $2))
    echo $((${da#-} + ${db#-}))
}

read A B Q

for (( i = 0; i < A; i++ )); do
    read v
    echo $v > val
    git commit -a -m "s$i::$v"
done
echo $INF > val
git commit -a -m "sMAX::$INF"

git checkout initial
echo $NINF > val
git add -A
git commit -m "t-1::$NINF"
git checkout -b temples
git tag temples-initial

for (( i = 0; i < B; i++ )); do
    read v
    echo -n $v > val
    git commit -a -m "t$i::$v"
done
echo $INF > val
git commit -a -m "tMAX::$INF"

for (( i = 0; i < Q; i++ )); do
    read x
    git bisect start
    git bisect good shrines-initial
    git bisect bad shrines
    git bisect run sh -c 'test $(cat val) -lt '$x
    sl=$(git log bisect/bad^ -1 | grep :: | sed -e 's/.\+:://' | tr -d '\n')
    sr=$(git log bisect/bad -1 | grep :: | sed -e 's/.\+:://' | tr -d '\n')

    git bisect reset
    git bisect start
    git bisect good temples-initial
    git bisect bad temples
    git bisect run sh -c 'test $(cat val) -lt '$x
    tl=$(git log bisect/bad^ -1 | grep :: | sed -e 's/.\+:://' | tr -d '\n')
    tr=$(git log bisect/bad -1 | grep :: | sed -e 's/.\+:://' | tr -d '\n')

    echo $(distance $x $sl $tl) > res
    echo $(distance $x $sl $tr) >> res
    echo $(distance $x $sr $tl) >> res
    echo $(distance $x $sr $tr) >> res
    echo $(distance $x $tl $sl) >> res
    echo $(distance $x $tl $sr) >> res
    echo $(distance $x $tr $sl) >> res
    echo $(distance $x $tr $sr) >> res
    ans=$(sort -n res | head -1)
    echo $ans 1>&3
    rm res
done
