Vsesib4

#include <iostream>
#include <vector>
#include <string>

constexpr  uint64_t del = 1e9 + 9;

uint64_t rec(const std::vector<std::pair<int, int>>& act, const std::vector<std::string>& moves, const int ind, const uint64_t val)
{
    if (moves[ind] == "x")
        return val;

    else if (moves[ind] == "+")
        return (rec(act, moves, act[ind].first, val) + rec(act, moves, act[ind].second, val)) % del;

    else if (moves[ind] == "*")
        return (rec(act, moves, act[ind].first, val) * rec(act, moves, act[ind].second, val)) % del;

    else
        return std::stoull(moves[ind]);
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int n = 0, m = 0, q = 0;
    std::cin >> n >> m >> q;

    std::vector<std::string> moves(n);

    for (auto& mo : moves)
        std::cin >> mo;

    std::vector<std::pair<int, int>> act(n, std::make_pair(-1, -1));

    while (m--)
    {
        int f = 0, s = 0;
        std::cin >> f >> s, f--, s--;
        act[s].first == -1 ? (act[s].first = f) : (act[s].second = f);
    }

    if (q == 0)
        std::cout << rec(act, moves, 0, 0);
    else
    {
        while (q--)
        {
            uint64_t elem = 0;
            std::cin >> elem;
            std::cout << rec(act, moves, 0, elem) << '\n';
        }
    }

    return 0;
}