paiza問題集の「2項間漸化式」のリファクタリング、入力チェック、テストコードを考えてみた

paizaラーニングレベルアップ問題集の2項間漸化式2の入力をやってみました。

---

問題

---

提出コード

#include <stdio.h>

int main(void) {
	int x, d;
	scanf("%d %d", &x, &d);
	int A[1000];
	A[0] = x;
	for (int i = 1; i < 1000; i++) {
		A[i] = A[i - 1] + d;
	}
	int Q;
	scanf("%d", &Q);
	while (Q--) {
		int k;
		scanf("%d", &k);
		printf("%d\n", A[k - 1]);
	}
	return 0;
}

---

ロジック部

プロトタイプ

初項$x$、公差$d$をコンストラクタに、添字$k_i$（$1\le i\le Q$）をメソッドに渡すクラスを作成します。

Sequence.h

#ifndef SEQUENCE_H_
#define SEQUENCE_H_

#include <stddef.h>
#include <stdbool.h>

typedef struct __Sequence _Sequence;

typedef struct Sequence {
	_Sequence *_seq;
	bool (*get)(const struct Sequence*, size_t, int*);
} Sequence;

Sequence* newSequence(int, int);

void freeSequence(Sequence**);

#endif /* SEQUENCE_H_ */

尚、getメソッドの第2引数には、標準入力で与えられた添字から1を引いた値（$0\le k<1000$）を渡す想定です。

---

テストコード

実装前、または実装と並行して、テストコードを作成します。
getメソッドの第2引数は$0\le k<1000$のみ受け付けることに注意します。
今回は単体テストツールとして、minunit.hを使用します。

SequenceTest.c

#include <stdio.h>
#include <string.h>
#include <errno.h>
#include "minunit.h"
#include "Sequence.h"

int tests_run = 0;

static char* message_d(int expected, int actual) {
	static char msg[72];
	snprintf(msg, sizeof(msg), "Error: expected: <%d> but was: <%d>", expected, actual);
	return msg;
}

static char* test_constructor_0() {return test_constructor(0, 0);}
static char* test_constructor_1() {return test_constructor(1, 1);}
static char* test_constructor_2() {return test_constructor(1000, 1000);}
static char* test_constructor_3() {return test_constructor(-1000, -1000);}

static char* test_get(int x, int d, size_t k, int expected) {
	Sequence *seq = newSequence(x, d);
	int actual;
	bool result = seq->get(seq, k, &actual);
	freeSequence(&seq);
	mu_assert("Error: expected: <true> but was: <false>", result);
	mu_assert(message_d(expected, actual), actual == expected);
	mu_assert(message_d(0, errno), errno == 0);
	return 0;
}

static char* test_get_out_of_range(int x, int d, size_t k) {
	Sequence *seq = newSequence(x, d);
	int actual;
	bool result = seq->get(seq, k, &actual);
	freeSequence(&seq);
	mu_assert("Error: expected: <false> but was: <true>", !result);
	mu_assert(message_d(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_get_0() {return test_get(0, 0, 0, 0);}
static char* test_get_1() {return test_get(1, 1, 1, 2);}
static char* test_get_2() {return test_get(1000, 1000, 999, 1000000);}
static char* test_get_3() {return test_get(-1000, -1000, 999, -1000000);}
static char* test_get_4() {return test_get_out_of_range(0, 0, 1000);}

static char* all_tests() {
	mu_run_test(test_get_0);
	mu_run_test(test_get_1);
	mu_run_test(test_get_2);
	mu_run_test(test_get_3);
	mu_run_test(test_get_4);
	return 0;
}

int main() {
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	return result != 0;
}

---

Windows環境の場合、以下のようなバッチファイルを作成しておけばテストしやすいでしょう。

SequenceTest.bat

echo off
gcc -Wall -Wextra -Werror -std=c99 SequenceTest.c Sequence.c -o SequenceTest 1>SequenceTest.txt 2>&1
if exist SequenceTest.exe (
	.\SequenceTest
	echo %ERRORLEVEL%
	del SequenceTest.exe
	del SequenceTest.txt
) else (
	type SequenceTest.txt
)
pause

---

ソースコード

前問の疑似コードを参考にして実装するとよいでしょう。
ただ、クエリが何回も来るので、コンストラクタで前計算しておきます。
テストコードを先に書く場合、テストをパスするようにコードを書くことも意識します。

Sequence.c

#include <stdlib.h>
#include <errno.h>

#include "Sequence.h"

const size_t K = 1000;

struct __Sequence {
	size_t size;
	int sequence[];
};

static bool Sequence_get(const struct Sequence *self, size_t k, int *a) {
	errno = 0;
	if (k >= K) {
		errno = ERANGE;
		return false;
	}
	*a = self->_seq->sequence[k];
	return true;
}

Sequence* newSequence(int x, int d) {
	errno = 0;
	Sequence *seq = malloc(sizeof(Sequence));
	if (!seq)
		return NULL;
	seq->_seq = malloc(sizeof(_Sequence) + sizeof(seq->_seq->sequence[0]) * K);
	if (!seq->_seq) {
		free(seq);
		return NULL;
	}
	seq->_seq->size = K;
	seq->_seq->sequence[0] = x;
	for (size_t i = 1; i < K; i++)
		seq->_seq->sequence[i] = seq->_seq->sequence[i - 1] + d;
	seq->get = Sequence_get;
	return seq;
}

void freeSequence(Sequence** self) {
	free((*self)->_seq);
	(*self)->_seq = NULL;
	free(*self);
	*self = NULL;
}

---

上記のように実装した場合、コンストラクタのテストは

• 不完全型へのポインタ
• $a_i=x+(i-1)d$

を用いればできないこともない、という程度です。インスタンスが生成されることを確認する程度でよいでしょう。

test_constructor

static char* message_zu(size_t expected, size_t actual) {
	static char msg[72];
	snprintf(msg, sizeof(msg), "Error: expected: <%zu> but was: <%zu>", expected, actual);
	return msg;
}

static char* test_constructor(int x, int d) {
	Sequence *seq = newSequence(x, d);
	mu_assert("Error: expected: not <null> but was: <null>", seq);
	void *p = (void*) seq->_seq;
	size_t size = *(size_t*)p;
	p += sizeof(size_t);
	int actual[size];
	memcpy(actual, p, sizeof(actual));
	freeSequence(&seq);
	mu_assert("Error: expected: <null> but was: not <null>", !seq);
	mu_assert(message_zu(1000, size), size == 1000);
	for (size_t i = 0; i < size; i++) {
		int expected = x + ((int) i) * d;
		mu_assert(message_d(expected, actual[i]), actual[i] == expected);
	}
	return 0;
}

---

入力チェック

問題集や競技プログラミングでは制約条件どおりの入力が与えられますが、実務ではそうとは限りません。そこで、入力チェックをする必要があります。

---

プロトタイプ

• 初項$x$、公差$d$
• クエリ数$Q$
• 添字$k$

を受け取る部分に分けます。クエリ数$Q$と添字$k$は共に1以上1000以下の数値が入力されますが、意味が異なるので関数を分けます（将来的に$Q$は100000まで許す、という時に$k$の入力チェックに影響を与えない）。

input.h

#ifndef INPUT_H_
#define INPUT_H_

#include <stdbool.h>

bool read_init(const char*, int*, int*);

bool read_query_num(const char*, size_t*);

bool read_index(const char*, size_t*);

#endif /* INPUT_H_ */

---

テストコード

• 数値以外の入力（今回は省略）
• 範囲外の入力（1001以上の入力等）

がはじけているかをテストします。

inputTest.c

#include <stdio.h>
#include <string.h>
#include <errno.h>
#include "minunit.h"
#include "input.h"

int tests_run = 0;

static char* message_zu(size_t expected, size_t actual) {
	static char msg[72];
	snprintf(msg, sizeof(msg), "Error: expected: <%zu> but was: <%zu>", expected, actual);
	return msg;
}

static char* message_d(int expected, int actual) {
	static char msg[72];
	snprintf(msg, sizeof(msg), "Error: expected: <%d> but was: <%d>", expected, actual);
	return msg;
}

static char* test_read_init(const char *str, int ex, int ed) {
	int x, d;
	mu_assert("Error: expected: <true> but was: <false>", read_init(str, &x, &d));
	mu_assert(message_d(ex, x), x == ex);
	mu_assert(message_d(ed, d), d == ed);
	mu_assert(message_d(0, errno), errno == 0);
	return 0;
}

static char* test_read_init_invalid(const char *str) {
	int x, d;
	mu_assert("Error: expected: <false> but was: <true>", !read_init(str, &x, &d));
	mu_assert(message_d(EINVAL, errno), errno == EINVAL);
	return 0;
}

static char* test_read_init_out_of_range(const char *str) {
	int x, d;
	mu_assert("Error: expected: <false> but was: <true>", !read_init(str, &x, &d));
	mu_assert(message_d(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_read_init_0() {return test_read_init_invalid(NULL);}
static char* test_read_init_1() {return test_read_init_invalid("");}
static char* test_read_init_2() {return test_read_init_invalid("0");}
static char* test_read_init_3() {return test_read_init_invalid("0 0 0");}
static char* test_read_init_4() {return test_read_init("0 0", 0, 0);}
static char* test_read_init_5() {return test_read_init_out_of_range("-1001 -1000");}
static char* test_read_init_6() {return test_read_init_out_of_range("-1000 -1001");}
static char* test_read_init_7() {return test_read_init("-1000 -1000", -1000, -1000);}
static char* test_read_init_8() {return test_read_init("1000 1000", 1000, 1000);}
static char* test_read_init_9() {return test_read_init_out_of_range("1001 1000");}
static char* test_read_init_10() {return test_read_init_out_of_range("1000 1001");}

static char* test_read_query_num(const char *str, size_t expected) {
	size_t actual;
	mu_assert("Error: expected: <true> but was: <false>", read_query_num(str, &actual));
	mu_assert(message_zu(expected, actual), actual == expected);
	mu_assert(message_d(0, errno), errno == 0);
	return 0;
}

static char* test_read_query_num_invalid(const char *str) {
	size_t actual;
	mu_assert("Error: expected: <false> but was: <true>", !read_query_num(str, &actual));
	mu_assert(message_d(EINVAL, errno), errno == EINVAL);
	return 0;
}

static char* test_read_query_num_out_of_range(const char *str) {
	size_t actual;
	mu_assert("Error: expected: <false> but was: <true>", !read_query_num(str, &actual));
	mu_assert(message_d(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_read_query_num_0() {return test_read_query_num_invalid(NULL);}
static char* test_read_query_num_1() {return test_read_query_num_invalid("");}
static char* test_read_query_num_2() {return test_read_query_num_out_of_range("0");}
static char* test_read_query_num_3() {return test_read_query_num("1", 1);}
static char* test_read_query_num_4() {return test_read_query_num("1000", 1000);}
static char* test_read_query_num_5() {return test_read_query_num_out_of_range("1001");}

static char* test_read_index(const char *str, size_t expected) {
	size_t actual;
	mu_assert("Error: expected: <true> but was: <false>", read_index(str, &actual));
	mu_assert(message_zu(expected, actual), actual == expected);
	mu_assert(message_d(0, errno), errno == 0);
	return 0;
}

static char* test_read_index_invalid(const char *str) {
	size_t actual;
	mu_assert("Error: expected: <false> but was: <true>", !read_index(str, &actual));
	mu_assert(message_d(EINVAL, errno), errno == EINVAL);
	return 0;
}

static char* test_read_index_out_of_range(const char *str) {
	size_t actual;
	mu_assert("Error: expected: <false> but was: <true>", !read_index(str, &actual));
	mu_assert(message_d(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_read_index_0() {return test_read_index_invalid(NULL);}
static char* test_read_index_1() {return test_read_index_invalid("");}
static char* test_read_index_2() {return test_read_index_out_of_range("0");}
static char* test_read_index_3() {return test_read_index("1", 1);}
static char* test_read_index_4() {return test_read_index("1000", 1000);}
static char* test_read_index_5() {return test_read_index_out_of_range("1001");}

static char* all_tests() {
	mu_run_test(test_read_init_0);
	mu_run_test(test_read_init_1);
	mu_run_test(test_read_init_2);
	mu_run_test(test_read_init_3);
	mu_run_test(test_read_init_4);
	mu_run_test(test_read_init_5);
	mu_run_test(test_read_init_6);
	mu_run_test(test_read_init_7);
	mu_run_test(test_read_init_8);
	mu_run_test(test_read_init_9);
	mu_run_test(test_read_init_10);
	mu_run_test(test_read_query_num_0);
	mu_run_test(test_read_query_num_1);
	mu_run_test(test_read_query_num_2);
	mu_run_test(test_read_query_num_3);
	mu_run_test(test_read_query_num_4);
	mu_run_test(test_read_query_num_5);
	mu_run_test(test_read_index_0);
	mu_run_test(test_read_index_1);
	mu_run_test(test_read_index_2);
	mu_run_test(test_read_index_3);
	mu_run_test(test_read_index_4);
	mu_run_test(test_read_index_5);
	return 0;
}

int main() {
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	return result != 0;
}

---

inputTest.bat

echo off
gcc -Wall -Wextra -Werror -std=c99 inputTest.c input.c util.c -o inputTest 1>inputTest.txt 2>&1
if exist inputTest.exe (
	.\inputTest
	echo %ERRORLEVEL%
	del inputTest.exe
	del inputTest.txt
) else (
	type inputTest.txt
)
pause

---

ソースコード

それぞれ

• $-1000\le x\le 1000$
• $-1000\le d\le 1000$
• $1\le Q\le 1000$
• $1\le k_i\le 1000$（$1\le i\le Q$）

の場合true、それ以外の場合falseとなる関数を実装します。
今回、以下の社内標準ライブラリ（仮：テスト済）を使うことにします。

util.h

util.h

#ifndef UTIL_H_
#define UTIL_H_
#include <stdint.h>
#include <stdbool.h>

char* chomp(char*);

bool parse_ulong(const char*, size_t*);

bool parse_int(const char*, int*);

#endif /* UTIL_H_ */

util.c

util.c

#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <inttypes.h>
#include <errno.h>
#include "util.h"

char* chomp(char *s) {
	if (!s)
		return NULL;
	size_t n = strlen(s);
	while (n--)
		if (isspace(s[n]))
			s[n] = '\0';
		else
			break;
	return s;
}

static bool is_positive_number(const char *s) {
	if (!(s && *s))
		return false;
	if (*s == '0')
		return s[1] == 0;
	for (const char *c = s; *c; c++)
		if (!isdigit(*c))
			return false;
	return true;
}

static bool is_number(const char *s) {
	if (!(s && *s))
		return false;
	if (*s == '-')
		return s[1] != 0 && s[1] != '0' && is_positive_number(s + 1);
	else
		return is_positive_number(s);
}

static bool parse_unsigned(const char *str, uintmax_t *u, uintmax_t max) {
	errno = 0;
	if (!is_positive_number(str)) {
		errno = EINVAL;
		return false;
	}
	char *s = NULL;
	*u = strtoumax(str, &s, 10);
	if (errno) {
		return false;
	} else if (s && *s) {
		errno = EINVAL;
		return false;
	} else if (*u > max) {
		errno = ERANGE;
		return false;
	}
	return true;
}

static bool parse_signed(const char *str, intmax_t *i, intmax_t max) {
	errno = 0;
	if (!is_number(str)) {
		errno = EINVAL;
		return false;
	}
	char *s = NULL;
	*i = strtoimax(str, &s, 10);
	if (errno) {
		return false;
	} else if (s && *s) {
		errno = EINVAL;
		return false;
	} else if (*i < ~max || max < *i) {
		errno = ERANGE;
		return false;
	}
	return true;
}

bool parse_ulong(const char *str, size_t *n) {
	uintmax_t m = 0;
	if (!parse_unsigned(str, &m, SIZE_MAX))
		return false;
	*n = (size_t) m;
	return true;
}

bool parse_int(const char *str, int *n) {
	intmax_t m = 0;
	if (!parse_signed(str, &m, INT_MAX))
		return false;
	*n = (int) m;
	return true;
}

---

#include <string.h>
#include <ctype.h>
#include <errno.h>
#include "input.h"
#include "util.h"

bool read_init(const char *str, int *x, int *d) {
	errno = 0;
	if (!(str && *str)) {
		errno = EINVAL;
		return false;
	}
	char s[] = "-1000 -1000\n";
	if (strlen(str) > strlen(s)) {
		errno = EINVAL;
		return false;
	}
	if (!parse_int(strtok(chomp(strncpy(s, str, sizeof(s) - 1)), " "), x)) {
		return false;
	} else if (*x < -1000 || 1000 < *x) {
		errno = ERANGE;
		return false;
	}
	if (!parse_int(strtok(NULL, " "), d)) {
		return false;
	} else if (*d < -1000 || 1000 < *d) {
		errno = ERANGE;
		return false;
	}
	if (strtok(NULL, " ")) {
		errno = EINVAL;
		return false;
	}
	return true;
}

bool read_query_num(const char *str, size_t *q) {
	errno = 0;
	if (!(str && *str)) {
		errno = EINVAL;
		return false;
	}
	char s[] = "1000\n";
	if (strlen(str) > strlen(s)) {
		errno = EINVAL;
		return false;
	}
	if (!parse_ulong(chomp(strncpy(s, str, sizeof(s) - 1)), q)) {
		return false;
	} else if (*q < 1 || 1000 < *q) {
		errno = ERANGE;
		return false;
	}
	return true;
}

bool read_index(const char *str, size_t *k) {
	errno = 0;
	if (!(str && *str)) {
		errno = EINVAL;
		return false;
	}
	char s[] = "1000\n";
	if (strlen(str) > strlen(s)) {
		errno = EINVAL;
		return false;
	}
	if (!parse_ulong(chomp(strncpy(s, str, sizeof(s) - 1)), k)) {
		return false;
	} else if (*k < 1 || 1000 < *k) {
		errno = ERANGE;
		return false;
	}
	return true;
}

---

エントリポイント

上述のSequence、inputを用いて、main関数を書き換えます。

---

テストコード

不正入力を検知した場合は再入力させる、ということも確認します。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>
#include <errno.h>
#include "minunit.h"
#define SOURCE "main"
#define IN_FILE "in.txt"
#define OUT_FILE "out.txt"
#define ERR_FILE "err.txt"

int tests_run = 0;
char result[1024][16];

static char* message_zu(size_t expected, size_t actual) {
	static char msg[72];
	snprintf(msg, sizeof(msg), "Error: expected: <%zu> but was: <%zu>", expected, actual);
	return msg;
}

static char* message_s(const char *expected, const char *actual) {
	static char msg[256];
	snprintf(msg, sizeof(msg), "Error: expected: <%s> but was: <%s>", expected, actual);
	return msg;
}

static char* message_d(int expected, int actual) {
	static char msg[72];
	snprintf(msg, sizeof(msg), "Error: expected: <%d> but was: <%d>", expected, actual);
	return msg;
}

static size_t test(size_t n, const char *lines[]) {
	FILE *file;
	if (!(file = fopen(IN_FILE, "w"))) {
		perror(NULL);
		exit(errno);
	}
	for (size_t i = 0; i < n; i++) {
		fputs(lines[i], file);
		fputc('\n', file);
	}
	fclose(file);
	clock_t clockt = clock();
	if (!!(errno = system(".\\" SOURCE " <" IN_FILE " 1>" OUT_FILE " 2>" ERR_FILE))) {
		perror(NULL);
		exit(errno);
	}
	fprintf(stderr, "#%d %f sec\n", tests_run, (float) (clock() - clockt) / CLOCKS_PER_SEC);
	fflush(stderr);
	if (!(file = fopen(OUT_FILE, "r"))) {
		perror(NULL);
		exit(errno);
	}
	size_t m = 0;
	while (fgets(result[m], sizeof(result[m]), file)) m++;
	fclose(file);
	return m;
}

static int test_err(size_t n, const char *lines[]) {
	FILE *file;
	if (!(file = fopen(IN_FILE, "w"))) {
		perror(NULL);
		exit(errno);
	}
	for (size_t i = 0; i < n; i++) {
		fputs(lines[i], file);
		fputc('\n', file);
	}
	fclose(file);
	clock_t clockt = clock();
	int e = system(".\\" SOURCE " <" IN_FILE " 1>" OUT_FILE " 2>" ERR_FILE);
	fprintf(stderr, "#%d %f sec\n", tests_run, (float) (clock() - clockt) / CLOCKS_PER_SEC);
	fflush(stderr);
	return e;
}

static char* test0() {
	int e = test_err(0, NULL);
	mu_assert(message_d(EXIT_FAILURE, e), e == EXIT_FAILURE);
	return 0;
}

static char* test1() {
	const char *lines[] = { "0 0", "1", "1" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_zu(1, n), n == 1);
	mu_assert(message_s("0\n", result[0]), !strcmp(result[0], "0\n"));
	return 0;
}

static char* test2() {
	const char *lines[] = {
		"0", "0 0 0", "1001 1000", "1000 1001", "-1001 -1000", "-1000 -1001", "0 0",
		"0", "1001", "1",
		"0", "1001", "1"
	};
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_zu(1, n), n == 1);
	mu_assert(message_s("0\n", result[0]), !strcmp(result[0], "0\n"));
	return 0;
}

static char* test3() {
	char *lines[1002] = { "-1000 -1000", "1000" };
	char str[1000][8] = { };
	for (size_t i = 0; i < 1000; i++) {
		snprintf(str[i], sizeof(str[i]), "%zu", i + 1);
		lines[i + 2] = str[i];
	}
	size_t n = test(sizeof(lines) / sizeof(lines[0]), (const char**) lines);
	mu_assert(message_zu(1000, n), n == 1000);
	for (size_t i = 0; i < 1000; i++) {
		char s[16] = { };
		snprintf(s, sizeof(s), "-%zu000\n", i + 1);
		mu_assert(message_s(s, result[i]), !strcmp(result[i], s));
	}
	return 0;
}

static char* all_tests() {
	mu_run_test(test0);
	mu_run_test(test1);
	mu_run_test(test2);
	mu_run_test(test3);
	return 0;
}

int main() {
	if (!!(errno = system("gcc -Wall -Wextra -Werror -DNDEBUG -std=c99 " SOURCE ".c Sequence.c input.c util.c -o " SOURCE " 1>" SOURCE ".txt 2>&1"))) {
		perror(NULL);
		FILE *file = fopen(SOURCE ".txt", "r");
		if (file) {
			int c = 0;
			while ((c = fgetc(file)) != EOF)
				putchar(c);
			fclose(file);
		}
		exit(errno);
	}
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	remove(ERR_FILE);
	remove(OUT_FILE);
	remove(IN_FILE);
	remove(SOURCE ".exe");
	remove(SOURCE ".txt");
	if (errno) {
		return errno;
	} else {
		return result != 0;
	}
}

---

test.bat

echo off
gcc -Wall -Wextra -Werror -std=c99 test.c -o test 1>test.txt 2>&1
if exist test.exe (
	.\test
	echo %ERRORLEVEL%
	del test.exe
	del test.txt
) else (
	type test.txt
)
pause

---

ソースコード

-DNDEBUGオプションにより、通常モード/時間計測モードを切り替えられるようにしてあります。

#include <stdio.h>
#include <stdlib.h>

#include "Sequence.h"
#ifdef NDEBUG
#include <string.h>
#include <errno.h>
#include "input.h"
const char END[] = { EOF, '\n', 0 };
#else
#include <time.h>
#define PRINT(format, ...)                      \
	do {                                        \
		fprintf(stderr, format, ##__VA_ARGS__); \
		fflush(stderr);                         \
	} while (0)
#endif

int main() {
#ifndef NDEBUG
	clock_t clockt = clock();
#endif
	int x, d;
#ifdef NDEBUG
	do {
		errno = 0;
		char s[] = "-1000 -1000\n";
		if (!fgets(s, sizeof(s), stdin)) {
			return EXIT_FAILURE;
		}
		if (!strchr(s, '\n')) {
			for (int c = getchar(); !strchr(END, c); c = getchar());
			errno = EINVAL;
		} else if (read_init(s, &x, &d)) {
			break;
		}
		perror(NULL);
	} while (true);
#else
	x = -1000;
	d = -1000;
#endif
	Sequence *seq = newSequence(x, d);
	size_t Q;
#ifdef NDEBUG
	do {
		errno = 0;
		char s[] = "1000\n";
		if (!fgets(s, sizeof(s), stdin)) {
			return EXIT_FAILURE;
		}
		if (!strchr(s, '\n')) {
			for (int c = getchar(); !strchr(END, c); c = getchar());
			errno = EINVAL;
		} else if (read_query_num(s, &Q)) {
			break;
		}
		perror(NULL);
	} while (true);
#else
	Q = 1000;
#endif
	while (Q--) {
		size_t k;
#ifdef NDEBUG
		do {
			errno = 0;
			char s[] = "1000\n";
			if (!fgets(s, sizeof(s), stdin)) {
				return EXIT_FAILURE;
			}
			if (!strchr(s, '\n')) {
				for (int c = getchar(); !strchr(END, c); c = getchar());
				errno = EINVAL;
			} else if (read_index(s, &k)) {
				break;
			}
			perror(NULL);
		} while (true);
#else
		k = 1000 - Q;
#endif
		int a;
		if (!seq->get(seq, --k, &a)) {
			freeSequence(&seq);
			return EXIT_FAILURE;
		}
		printf("%d\n", a);
	}
	freeSequence(&seq);
#ifndef NDEBUG
	PRINT("%f sec.\n", (float) (clock() - clockt) / CLOCKS_PER_SEC);
#endif
	return EXIT_SUCCESS;
}