// Arup Guha
// 12/6/2013
// Very clunky solution to CIS 3362 Homework #4
// Reused for CIS 3362 Fall 2021 Homework #7

import java.util.*;
import java.math.*;

class GDHNode {

	// I just store everything this node needs...there is definitely a better way; some of this stuff should be static.
	public BigInteger p;
	public BigInteger g;
	public String ID;
	public BigInteger key;
	public GDHNode left;
	public GDHNode right;
	public GDHNode parent;

	// Creates a leaf node only.
	public GDHNode(String name, BigInteger secret, BigInteger prime, BigInteger gen) {
		p = prime;
		g = gen;
		ID = name;
		key = secret;
		left = null;
		right = null;
	}

	// Creates a new key given direct children leftTree and rightTree.
	public GDHNode(String keyName, GDHNode leftTree, GDHNode rightTree) {

		// All of this directly follows...
		ID = keyName;
		left = leftTree;
		right = rightTree;
		p = left.p;
		g = left.g;
		left.parent = this;
		right.parent = this;
		parent = null;

		// This is the desired key calculation.
		key = (g.modPow(left.key, p)).modPow(right.key, p);
	}

	// Adds the node newNode to this node as a sponsor node and updates map accordingly.
	public void sponsor(String keyName, GDHNode newNode, HashMap<String,GDHNode> map) {

		// Save the parent AND which side this node is of the parent.
		GDHNode saveParent = this.parent;
		boolean isLeft = true;
		if (saveParent.right == this)
			isLeft = false;

		// This will be the new node that gets created and will be located "physically" where this used to be.
		GDHNode newKey = new GDHNode(keyName, this, newNode);

		// Link the parent of the new node properly to its new child, newKey.
		if (isLeft)
			saveParent.left = newKey;
		else
			saveParent.right = newKey;

		// Bookkeeping: update our map and store the parent of newKey.
		map.put(keyName, newKey);
		newKey.parent = saveParent;
		newKey.fixKeys();
	}

	// Recalculates keys for ancestral path from this node up.
	public void fixKeys() {

		// March up the tree, recalculating each key until we reach the root.
		GDHNode temp = parent;
		while (temp != null) {
			temp.key = (g.modPow(temp.left.key, p)).modPow(temp.right.key, p);
			temp = temp.parent;
		}
	}

	public boolean isLeaf() {
		return left == null && right == null;
	}

	// Precondition: Will NOT change the main root of the tree to which this node belongs.
	// Deletes this item from the bigger GDH Tree and if necessary uses newKey for the sibling node.
	public void delete(BigInteger newKey) {

		// Identify and get pointers to both the parent and sibling nodes.
		GDHNode parentOfDel = this.parent;
		GDHNode grandpa = parentOfDel.parent;
		GDHNode sibling = null;
		if (parentOfDel.left == this)
			sibling = parentOfDel.right;
		else
			sibling = parentOfDel.left;

		// We'll need to know later which side of grandpa the parent is...
		boolean grandpaLeft = false;
		if (grandpa.left == parentOfDel)
			grandpaLeft = true;

		// Case where we assign a new key.
		if (sibling.isLeaf()) sibling.key = newKey;

		// In either case, we must bypass the old parent node and attach the grandpa to the sibling.
		if (grandpaLeft)
			grandpa.left = sibling;
		else
			grandpa.right = sibling;

		// Last, but not least, propagate up new keys.
		sibling.fixKeys();
	}
}

public class GroupDH {

	public BigInteger p;
	public BigInteger g;
	public GDHNode root;
	public HashMap<String,GDHNode> map;

	// Sort of a wrapper object to store one whole system.
	public GroupDH(BigInteger prime, BigInteger gen) {
		p = prime;
		g = gen;
		root = null;
		map = new HashMap<String,GDHNode>();
	}

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		BigInteger p = new BigInteger(stdin.next());
		BigInteger g = new BigInteger(stdin.next());
		GroupDH keys = new GroupDH(p,g);

		// Read in number of commands.
		int n = stdin.nextInt();

		// Set up the beginning tree.
		String name1 = stdin.next();
		BigInteger secret1 = new BigInteger(stdin.next());
		String name2 = stdin.next();
		BigInteger secret2 = new BigInteger(stdin.next());
		String keyName = stdin.next();
		GDHNode rootLeft = new GDHNode(name1, secret1, p, g);
		GDHNode rootRight = new GDHNode(name2, secret2, p, g);
		keys.root = new GDHNode(keyName, rootLeft, rootRight);
		keys.map.put(name1, rootLeft);
		keys.map.put(name2, rootRight);
		keys.map.put(keyName, keys.root);

		// Go through each command.
		for (int loop=0; loop<n-1; loop++) {

			String command = stdin.next();

			// Queries are easy - just use the hashmap to locate the node and return its key.
			if (command.equals("QUERY")) {
				keyName = stdin.next();
				GDHNode item = keys.map.get(keyName);
				System.out.println(item.key);
			}

			// Adding a node...
			else if (command.equals("ADD")) {

				// Reading in all the necessary information for the add.
				String sponsorName = stdin.next();
				BigInteger sponsorKey = new BigInteger(stdin.next());
				String newName = stdin.next();
				BigInteger newKey = new BigInteger(stdin.next());

				// This is the new node storing the new user.
				GDHNode newChild = new GDHNode(newName, newKey, p, g);
				//System.out.println("Creating new node "+newName+" with key "+ newKey);

				// Update our map.
				keys.map.put(newName, newChild);

				// Read in the name of our new key.
				keyName = stdin.next();

				// Retrieve the sponsor node, so we can do our add.
				GDHNode item = keys.map.get(sponsorName);

				// First we change our key (this is pretty bad design on my part...)
				item.key = sponsorKey;

				// Then we can do the sponsorship on this node.
				item.sponsor(keyName, newChild, keys.map);
			}

			else if (command.equals("DEL")) {

				String user = stdin.next();
				BigInteger newKey = new BigInteger(stdin.next());

				GDHNode itemToDel = keys.map.get(user);
				itemToDel.delete(newKey);
			}
		}
	}
}