Persistent Data Structures
If you're not familiar with persistent data structures, don't worry—you can still solve this problem.
Persistent data structures are those that allow you to access previous versions of the structure even after modifications. Imagine you have a sequence of n elements, and you need to replace the p-th element. To do this, you create a new version of the structure that is identical to the previous one, except for the p-th element. Consequently, you end up with two versions of the sequence.
In this problem, your task is to count how many versions of the sequence will be stored after executing m queries.
Input
The first line contains two integers n (1 ≤ n ≤ 100000) and m (1 ≤ m ≤ 100000), where n is the number of elements in the sequence, and m is the number of queries.
The second line contains n natural numbers, representing the sequence itself.
The next m lines contain queries of two types:
SET i p d — create a new sequence from sequence i, where the p-th element is set to d;
GET i p — retrieve the p-th element from sequence i.
The initial sequence is numbered 0. Positions in the sequence start from one. There will be no queries for non-existent versions. When processing a query of the first type, a new version is created, which is assigned the number j+1, where j is the number of the last added sequence, starting with j = 0.
Output
Output a single number—the total number of versions of the sequence.